Word Break II

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

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"

Tips:

如果要返回所有解法，则需要用到DFS。而直接DFS会超时，因为每一个位置都要dfs下去看有没有解。所以用hashmap来记录已经得到过的结果。把s分为左边和右边，如果左边在字典中，就DFS右边，DFS完返回一个sublist，然后result里加入左边的word和右边的sublist。需要注意的是，如果右边为空，则需要加入“”，不然结果会为空。

Complexity: O(len(wordDict) ^ len(s / minWordLenInDict)) There're len(wordDict) possibilities for each cut

Code：

    public class Solution {
        public List<String> wordBreak(String s, List<String> wordDict) {
            return DFS(s, wordDict, new HashMap<String, List<String>>());
        }
        private List<String> DFS(String s, List<String> wordDict, HashMap<String, List<String>> map) {
            if (map.containsKey(s)) return map.get(s);
            List<String> res = new ArrayList<>();
            if (s.length() == 0) {
                res.add("");
                return res;
            }
            for (String word : wordDict) {
                if (s.startsWith(word)) {
                    List<String> subList = DFS(s.substring(word.length()), wordDict, map);
                    for (String sub : subList) {
                        res.add(word + (sub.isEmpty() ? "" : " ") + sub);
                    }
                }
            }
            map.put(s, res);
            return res;
        }
    }

DP:

DP + DFS. Very similar to Word Break I, but instead of using a boolean dp array, I used an array of Lists to maintain all of the valid start positions for every end position. Then just do classic backtracking to find all solutions. The time complexity is O(nm) + O(n number of solutions), where n is the length of the input string, m is the length of the longest word in the dictionary. The run time was 6ms. It is very efficient because DP is used to find out all the valid answers, and no time is wasted on doing the backtracking.

public List<String> wordBreak(String s, Set<String> wordDict) {
    List<Integer>[] starts = new List[s.length() + 1]; // valid start positions
    starts[0] = new ArrayList<Integer>();

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

    List<String> rst = new ArrayList<>();
    if (starts[s.length()] == null) {
        return rst;
    }

    dfs(rst, "", s, starts, s.length());
    return rst;
}


private void dfs(List<String> rst, String path, String s, List<Integer>[] starts, int end) {
    if (end == 0) {
        rst.add(path.substring(1));
        return;
    }

    for (Integer start: starts[end]) {
        String word = s.substring(start, end);
        dfs(rst, " " + word + path, s, starts, start);
    }
}

private int getMaxLen(Set<String> wordDict) {
    int max = 0;
    for (String s : wordDict) {
        max = Math.max(max, s.length());
    }
    return max;
} 

Brute force:(2^n)

    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;
            }
            dfshelper(res , "" , 0 , wordDict , s);
            return res;
        }

        protected void dfshelper(List<String> res , String path , int start , Set<String> wordDict , String s) {
            if(start == s.length()) {
                res.add(path);
                return;
            }
            for(int i = start ; i < s.length() ; i++) {
                String t = s.substring(start , i+1);
                if(wordDict.contains(t)) {
                    if(i+1 != s.length()) {
                        path += t + " ";
                        dfshelper(res , path , i+1 , wordDict , s);
                        path = path.substring(0 , path.length() - t.length() - 1);
                    }else {
                        path += t;
                        dfshelper(res , path , i+1 , wordDict , s);
                        path = path.substring(0 , path.length() - t.length());                    
                    }
                }
            }
        }
    }