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, givens = “catsanddog”,dict = [“cat”, “cats”, “and”, “sand”, “dog”]

A solution is [“cats and dog”, “cat sand dog”]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

 // Memoriezed backtracking(DFS)
    // Using DFS directly will lead to TLE, so I just used HashMap to save the previous results to prune duplicated branches, as the following:
    public List<String> wordBreak(String s, Set<String> wordDict) {
        return backtrack(s, wordDict, new HashMap<String, LinkedList<String>>());
    }
    
    public List<String> backtrack(String s, Set<String> wordDict, HashMap<String, LinkedList<String>> map) {
        if (map.containsKey(s)) {
            return map.get(s);
        } 
        LinkedList<String> res = new LinkedList<String>();
        if (s.length() == 0) {
            res.add("");
            return res;
        }
        for (String word : wordDict) {
            if (s.startsWith(word)) {
                List<String> sublist = backtrack(s.substring(word.length()), wordDict, map);
                for (String sub : sublist) {
                    res.add(word + (sub.isEmpty() ? "" : " ") + sub);
                }
            }
        }
        map.put(s, res);
        return res;
    }