package com.interview.dynamic;

import java.util.HashSet;
import java.util.Set;

/**
 * Date 08/01/2014
 * @author tusroy
 * 
 * Given a string and a dictionary, split this string into multiple words such that
 * each word belongs in dictionary.
 * 
 * e.g peanutbutter -> pea nut butter
 * e.g Iliketoplay -> I like to play
 * 
 * Solution 
 * DP solution to this problem
 * if( input[i...j] belongs in dictionary) T[i][j] = i
 * else{
 *     T[i][j] = k if T[i][k-1] != -1 && T[k][j] != -1
 *     
 * Test cases
 * 1) Empty string
 * 2) String where entire string is in dictionary
 * 3) String which cannot be split into words which are in dictionary
 * 3) String which can be split into words which are in dictionary    
 *
 */
public class BreakMultipleWordsWithNoSpaceIntoSpace {

    
    /**
     * Recursive and slow version of breaking word problem.
     * If no words can be formed it returns null
     */
    public String breakWord(char[] str,int low,Set<String> dictionary){
        StringBuffer buff = new StringBuffer();
        for(int i= low; i < str.length; i++){
            buff.append(str[i]);
            if(dictionary.contains(buff.toString())){
                String result = breakWord(str, i+1, dictionary);
                if(result != null){
                    return buff.toString() + " " + result;
                }
            }
        }
        if(dictionary.contains(buff.toString())){
            return buff.toString();
        }
        return null;
    }
    
    /**
     * Dynamic programming version for breaking word problem.
     * It returns null string if string cannot be broken into multipe words
     * such that each word is in dictionary.
     * Gives preference to longer words over splits
     * e.g peanutbutter with dict{pea nut butter peanut} it would result in
     * peanut butter instead of pea nut butter.
     */
    public String breakWordDP(String word, Set<String> dict){
        int T[][] = new int[word.length()][word.length()];
        
        for(int i=0; i < T.length; i++){
            for(int j=0; j < T[i].length ; j++){
                T[i][j] = -1; //-1 indicates string between i to j cannot be split
            }
        }
        
        //fill up the matrix in bottom up manner
        for(int l = 1; l <= word.length(); l++){
            for(int i=0; i < word.length() -l + 1 ; i++){
                int j = i + l-1;
                String str = word.substring(i,j+1);
                //if string between i to j is in dictionary T[i][j] is true
                if(dict.contains(str)){
                    T[i][j] = i;
                    continue;
                }
                //find a k between i+1 to j such that T[i][k-1] && T[k][j] are both true 
                for(int k=i+1; k <= j; k++){
                    if(T[i][k-1] != -1 && T[k][j] != -1){
                        T[i][j] = k;
                        break;
                    }
                }
            }
        }
        if(T[0][word.length()-1] == -1){
            return null;
        }
        
        //create space separate word from string is possible
        StringBuffer buffer = new StringBuffer();
        int i = 0; int j = word.length() -1;
        while(i < j){
            int k = T[i][j];
            if(i == k){
                buffer.append(word.substring(i, j+1));
                break;
            }
            buffer.append(word.substring(i,k) + " ");
            i = k;
        }
        
        return buffer.toString();
    }

    
    public static void main(String args[]){
        Set<String> dictionary = new HashSet<String>();
        dictionary.add("I");
        dictionary.add("like");
        dictionary.add("had");
        dictionary.add("play");
        dictionary.add("to");
        String str = "Ihadliketoplay";
        BreakMultipleWordsWithNoSpaceIntoSpace bmw = new BreakMultipleWordsWithNoSpaceIntoSpace();
        String result1 = bmw.breakWordDP(str, dictionary);
        
        System.out.print(result1);
    }
}

@@ -46,37 +46,9 @@
 til.
-HashSet;%0Aimport java.util.Set
+*
 ;%0A%0A/
@@ -3479,16 +3479,1355 @@
 %0A    %7D%0A%0A
+    /**%0A     * Prints all the words possible instead of just one combination.%0A     * Reference%0A     * https://leetcode.com/problems/word-break-ii/%0A     */%0A    public List%3CString%3E wordBreakTopDown(String s, Set%3CString%3E wordDict) %7B%0A        Map%3CInteger, List%3CString%3E%3E dp = new HashMap%3C%3E();%0A        int max = 0;%0A        for (String s1 : wordDict) %7B%0A            max = Math.max(max, s1.length());%0A        %7D%0A        return wordBreakUtil(s, wordDict, dp, 0, max);%0A    %7D%0A%0A    private List%3CString%3E wordBreakUtil(String s, Set%3CString%3E dict, Map%3CInteger, List%3CString%3E%3E dp, int start, int max) %7B%0A        if (start == s.length()) %7B%0A            return Collections.singletonList(%22%22);%0A        %7D%0A%0A        if (dp.containsKey(start)) %7B%0A            return dp.get(start);%0A        %7D%0A%0A        List%3CString%3E words = new ArrayList%3C%3E();%0A        for (int i = start; i %3C start + max && i %3C s.length(); i++) %7B%0A            String newWord = s.substring(start, i + 1);%0A            if (!dict.contains(newWord)) %7B%0A                continue;%0A            %7D%0A            List%3CString%3E result = wordBreakUtil(s, dict, dp, i + 1, max);%0A            for (String word : result) %7B%0A                String extraSpace = word.length() == 0 ? %22%22 : %22 %22;%0A                words.add(newWord + extraSpace + word);%0A            %7D%0A        %7D%0A        dp.put(start, words);%0A        return words;%0A    %7D%0A%0A
     %0A   

add another method in word break problem