140. Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Solution:

1.DP

Similar to word break I, instead of tracking true/false for breaking into segments, dp[i] holds an ArrayList of all strings it can compose from 0 to i-1.

1. check if the string can be segmented using word break I algorithm, if not return. ---> to pass the time exceeded problem.
2. initialize an array of List$$<$$String$$>$$ as dp function. tmp[i] represent the strings it can compose from position 0 to i-1. List tmp[] = new ArrayList[s.length() + 1];
3. index i, j: i traverse from 0 to string end, j traverse from 0 to i, if tmp[j] contains strings and substring(j, i) is in the dictionary, update the tmp[i]'s arrayList
4. time: O(n^2*k), space: O(nk) (k is the average length of word)

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String> res = new ArrayList<String>();
        if(s == null || s.length() == 0){
            return res;
        }

        boolean[] f = new boolean[s.length() + 1];
        f[0] = true;
        for(int i = 0; i < s.length(); i++){
            for(int j = i; j >= 0; j--){
                if(f[j] && wordDict.contains(s.substring(j, i+1))){
                    f[i+1] = true;
                }
            }
        }

        if(!f[s.length()]){
            return res;
        }


        List<String> tmp[] = new ArrayList[s.length() + 1];
        tmp[0] = new ArrayList<String>();
        tmp[0].add("");

        for(int i = 0; i < s.length(); i++){
            for(int j = i; j >= 0; j--){
                if(wordDict.contains(s.substring(j,i+1)) && tmp[j] != null){

                    if(tmp[i+1] == null){
                        tmp[i+1] = new ArrayList<String>();
                    }

                    for(int k = tmp[j].size()-1; k >= 0; k--){
                        String curr = "";
                        if(i != s.length() - 1){
                            curr += tmp[j].get(k) + s.substring(j, i+1) + " ";
                        }else{
                            curr += tmp[j].get(k) + s.substring(j, i+1);
                        }
                        tmp[i+1].add(curr);
                    }
                }
            }
        }
        return tmp[tmp.length - 1]== null ? new ArrayList() : tmp[tmp.length - 1];
    }
}

2. DFS

Using an array of arrayList to hold the words at can be segmented at position i, using dfs to traverse back forth from the end of the string to the start, to print all possible results.

1. Here dfs start from the end of the array so that the next position can be found at (i - word.length). (if traverse from start to the end, each time needs go from start + 1 to next position idx to find the next word)
2. time: O(2^n), space: O(n)

public List<String> wordBreak(String s, Set<String> wordDict) {
    List<String> tmp[] = new ArrayList[s.length() + 1];
    tmp[0] = new ArrayList<String>();
    tmp[0].add("");

    for(int i = 0; i < s.length(); i++){
        for(int j = i; j >= 0; j--){
            if(wordDict.contains(s.substring(j,i+1)) && tmp[j] != null){        
                if(tmp[i+1] == null){
                    tmp[i+1] = new ArrayList<String>();
                }    
                tmp[i+1].add(s.substring(j,i+1));
            }
        }
    }

    List<String> result = new LinkedList<String>();
    if(tmp[s.length()] == null) 
        return result; 

    ArrayList<String> temp = new ArrayList<String>();
    dfs(tmp, s.length(), result, temp);

    return result;
}

public static void dfs(List<String> dp[],int end,List<String> result, ArrayList<String> tmp){
    //reverse the whole path
    if(end <= 0){
        String path = tmp.get(tmp.size()-1);
        for(int i=tmp.size()-2; i>=0; i--){
            path += " " + tmp.get(i) ;
        }

        result.add(path);
        return;
    }

    for(String str : dp[end]){
        tmp.add(str);
        dfs(dp, end-str.length(), result, tmp);
        tmp.remove(tmp.size()-1);
    }
}

Reference: https://segmentfault.com/a/1190000004236294 http://www.programcreek.com/2014/03/leetcode-word-break-ii-java/