LeetCode 140 Word Break II

LeetCode 140 Word Break II

<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模板：

1. key为子问题索引st，value为子问题的解。不含path和res因为类似于Catalan(属于单边Catalan)，用子问题返回结果来组成此轮结果。f(input, st, endIndex, cache)
2. 紧跟终结条件，若在cache中，返回子问题的解。
3. 循环结束，将子问题的结果存于cache。

注意事项：

1. 终止条件返回['']而不是[]，正如L017，空字符串作为初始结果。返回到上层要strip(), 因为ss可能为空
2. 子问题用f=word + f并不是f=f + word, 这样最后结果避免反转。
3. s[:i + 1]判断是否在字典中，而不是s[:i]，单词包括整个字符串。

Python代码：

def 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

注意事项：

1. 将两个输入都转换成小写。
2. 复制子问题的解，不能直接在解List<String>上编辑。

Java代码：

public 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(解大小)。