LeetCode 140 Word Break II

LeetCode 140 Word Break II

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:

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: []

题目大意：

一个字符串s，求被“字典集合”（wordDict）中的单词拼接的所有方案。

解题思路：

这是经典题。求所有可能性想到DFS，前面Lintcode 683提到可能会有重复解。所以用Cache。

Cache模板：

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

注意事项：

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

Python代码：

def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
	wordSet = set()
	for word in wordDict:
		wordSet.add(word)
	cache = {}
	res = self.dfs(s, wordSet, cache)
	return [] if len(res) == 1 and not res[0] else res

def dfs(self, s, wordSet, cache):
	if not s:
		return ['']
	if s in cache:
		return cache[s]
	res = []
	for i in range(len(s)):
		if s[:i + 1] not in wordSet:
			continue
		li = self.dfs(s[i + 1:], wordSet, cache)
		for ss in li:
			res.append((s[:i + 1] + ' ' + ss).strip())

	cache[s] = res
	return res

注意事项：

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

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