Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
**Input:** s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
**Output:** ["cats and dog","cat sand dog"]
Example 2:
**Input:** s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
**Output:** ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
**Explanation:** Note that you are allowed to reuse a dictionary word.
Example 3:
**Input:** s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
**Output:** []
Constraints:
1 <= s.length <= 20
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 10
s and wordDict[i] consist of only lowercase English letters.
All the strings of wordDict are unique.
ac1: DFS with memorization
Complexity: worst case is O(2^n), e.g. input "aaaaaa", with wordDict = ["a", "aa", "aaa", "aaaa", "aaaaa", "aaaaa"]. Every possible partition is a valid sentence, and there are 2^n-1 such partitions.
With cache, the runtime improves from O(2^n) to O(n^2), e.g. "aaaaab", with wordDict = ["a", "aa", "aaa", "aaaa", "aaaaa", "aaaaa"]. Why O(n^2)? Think reversely, it's just like finding valid partitions like O(n^2) DP in 0139. Word Break.
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
// edge cases
if (s == null || wordDict == null || s.length() == 0 || wordDict.size() == 0)
return new ArrayList<String>();
Set<String> dict = new HashSet<String>(wordDict);
Map<Integer,List<String>> map = new HashMap<Integer,List<String>>();
return dfs(s, 0, dict, map);
}
private List<String> dfs(String s, int start, Set<String> dict, Map<Integer,List<String>> map) {
List<String> res = new ArrayList<String>();
// exit
if (start == s.length()) res.add(""); // reach the end, validate string
// check map, avoid repeated work
if (map.containsKey(start)) return map.get(start);
// process
for (int e = start + 1; e <= s.length(); e++) {
String w = s.substring(start, e);
if (dict.contains(w)) {
List<String> next = dfs(s, e, dict, map);
for (String str : next) {
res.add(w + (str.equals("") ? "" : " ") + str);
}
}
}
map.put(start, res);
return res;
}
}
/*
DFS, memorization
iterate characters, if in dict, dfs check remaining:
if substring is validate, it returns word list, append all
else return empty list
*/