<div>
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. Return all such possible sentences.
Note:
- The same word in the dictionary may be reused multiple times in the segmentation.
- You may assume the dictionary does not contain duplicate words.
Example 1:
<pre>Input: s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output: [ "cats and dog", "cat sand dog" ]
</pre>
Example 2:
<pre>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. </pre>
Example 3:
<pre>Input: s = "catsandog" wordDict = ["cats", "dog", "sand", "and", "cat"] Output: []</pre>
</div>
题目大意：
一个字符串s，求被“字典集合”（wordDict）中的单词拼接的所有方案。
解题思路：
这是经典题。求所有可能性想到DFS，前面Lintcode 683提到可能会有重复解。所以用Cache。
Cache模板：
- key为子问题索引st，value为子问题的解。不含path和res因为类似于Catalan(属于单边Catalan)，用子问题返回结果来组成此轮结果。f(input, st, endIndex, cache)
- 紧跟终结条件，若在cache中，返回子问题的解。
- 循环结束，将子问题的结果存于cache。
注意事项：
- 终止条件返回['']而不是[]，正如L017，空字符串作为初始结果。返回到上层要strip(), 因为ss可能为空
- 子问题用f=word + f并不是f=f + word, 这样最后结果避免反转。
- s[:i + 1]判断是否在字典中，而不是s[:i]，单词包括整个字符串。
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
word_set = set(wordDict)
res = []
cache = {}
res = self.dfs(s, word_set, cache) #cat
return res
# dfs(s) = word + dfs(s[i+1:])
def dfs(self, s, word_set, cache):
if s == "":
return [""]
if s in cache:
return cache[s]
res = []
for i in range(len(s)):
if s[:i + 1] not in word_set:
continue
cur_list = self.dfs(s[i + 1:], word_set, cache) # i = 2, dfs("")
for _s in cur_list: # [""]
res.append((s[:i + 1] + " " + _s).strip()) #cat
cache[s] = res
return res
注意事项：
- 将两个输入都转换成小写。
- 复制子问题的解，不能直接在解List<String>上编辑。
Java代码：
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
27
28
29
30
31public List<String> wordBreak(String s, List<String> wordDict) {
List<String> res = new ArrayList<>();
if(s == null || s.isEmpty())
return res;
Set<String> wordDictLower = new HashSet<>();
for(String c : wordDict)
wordDictLower.add(c.toLowerCase());
s = s.toLowerCase();
Map<Integer, List<String>> cache = new HashMap<>();
return dfs(s, wordDictLower, s.length(), cache);
}
List<String> dfs(String s, Set<String> wordDict, int st, Map<Integer, List<String>> cache) {
if(st == 0)
return new ArrayList<>(Arrays.asList(""));
if(cache.containsKey(st))
return cache.get(st);
List<String> result = new ArrayList<>();
for(int i = 0; i < st; i++) {
String word = s.substring(i, st);
if(!wordDict.contains(word))
continue;
List<String> sub = dfs(s, wordDict, i, cache);
// copy solution for subproblem, don't edit on sub
for(int j = 0; j < sub.size(); j++)
result.add((sub.get(j) + " " + word).trim());
}
cache.put(st, result);
return result;
}
算法分析：
时间复杂度为O(解大小)，空间复杂度为O(解大小)。
