Description

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"].

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Solution

Recursion with memo, time O(n ^ 3), space O(n ^ 3)

public class Solution {
    private Map<Integer, List<String>> cache = new HashMap<>();
    
    public List<String> wordBreak(String s, List<String> wordDict) {
        return wordBreak(s, new HashSet<>(wordDict));
    }
    
    public List<String> wordBreak(String s, Set<String> wordDict) {
        return wordBreak(s, wordDict, 0);
    }
    
    public List<String> wordBreak(String s, Set<String> wordDict, int start) {
        if (cache.containsKey(start)) {
            return cache.get(start);
        }
        
        List<String> res = new LinkedList<>();
        if (start == s.length()) {
            res.add("");
        }
       
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end))) {
                List<String> list = wordBreak(s, wordDict, end);
                for (String l : list) {
                    res.add(s.substring(start, end) + (l.equals("") ? "" : " ") + l);
                }
            }
        }
        
        cache.put(start, res);
        return res;
    }
}

DP, time O(n ^ 3, space O(n ^ 3) (TLE)

Recursion with memo能AC，但是DP会TLE也是醉醉的...考虑下面这个test case:

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

Now I find answers to my own question. The bottom up DP solution is good solution only when we know where to start and which branches are valuable to global result. For this problem, an memorization search would be a good answer as we would only spend time on where in need. In detail, The reason that DP method Time Limit Exceeded is that the method computed too much time in invalid branches. There are many intermediate lists which will not construct final result. At the time of computing these lists, we did not know whether it will be included in final result, as a result, my suggestion is that, if we really want to solve this problem using DP, instead of spending O(k) time, where k is the length of the intermediate list, we could have just spend o(1) time by only storing the previous one degree indexes based on which we could rebuild the result string list, instead of computing the result string list. This is quite similar to the problem Word Ladder II.

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        List<String>[] dp = new LinkedList[s.length() + 1];
        List<String> initial = new LinkedList<>();
        initial.add("");
        dp[0] = initial;
        
        for (int i = 1; i <= s.length(); ++i) {
            dp[i] = new LinkedList<>();
            
            for (int j = i - 1; j >= 0; --j) {
                String word = s.substring(j, i);
                
                if (!wordDict.contains(word)) {
                    continue;
                }
                
                for (String sentence : dp[j]) {
                    sentence += (sentence.isEmpty() ? "" : " ") + word;
                    dp[i].add(sentence);
                }
            }
        }
        
        return dp[s.length()];
    }
}