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"]
// 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;
}
