LeetCode 139 Word Break

LeetCode 139 Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

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 = “leetcode”, wordDict = [“leet”, “code”]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = “applepenapple”, wordDict = [“apple”, “pen”]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
Output: false

题目大意：

一个字符串s，是否能够被“字典集合”（wordDict）中的单词拼接而成。

解题思路：

这是经典题。如果知道s[0:n-1)很容易知道s[0:n)是否有解，既然和子问题有关，就用DP。

1. 定义dp[i]为字符串s[0,i)是否可以合法分解。
2. 判断一个字符串是否可以合法分解，方案是尝试在每一位进行分解，若其中一个可分解，即有解。
   递归式为dp[i] |= dp[k] && isWord(s[k:i)), 0 <= k < i.
3. 方向为从左到右i=0..n, 初始值为dp[0] = true.

注意事项：

1. 初始值dp[0] = True。
2. 递归中dp[i]用或操作符。
3. s[j:i] in word_set不要忘记上限为i

Python代码：

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
	if not s:
		return False
	word_set = set(wordDict)
	dp = [False] * (len(s) + 1)
	dp[0] = True
	for i in range(1, len(dp)):
		for j in range(0, i):
			dp[i] |= dp[j] and s[j:i] in word_set
	return dp[len(dp) - 1]

注意事项：

1. 将两个输入都转换成小写。
2. 递归中dp[i]用或操作符。

Java代码：

public boolean wordBreak(String s, List<String> wordDict) {
	if(s == null || s.isEmpty() || wordDict == null || wordDict.size() == 0)
		return false;
	Set<String> wordDictLower = new HashSet<>();
	for(String c : wordDict)
		wordDictLower.add(c.toLowerCase());
	s = s.toLowerCase();
	
	boolean[] dp = new boolean[s.length() + 1];
	dp[0] = true;
	for(int i = 1; i < dp.length; i++)
		for(int k = 0; k < i; k++) {//"a"
			dp[i] |= dp[k] && wordDictLower.contains(s.substring(k, i));
		}
	return dp[dp.length - 1];
}

算法分析：

时间复杂度为O(n2)，空间复杂度为O(n)。

---

算法II解题思路：

这题也可以额用DFS来解。如果可以用DP就尽量用DP，只有求所有可能性才只能用DFS而不能用DP。
这道题递归子问题dfs[:n]为子串[0:n)是否可合法拆解。对于子问题而言，需要对其范围内i=[0:st)的每个可能位置分解
dfs[:i) + word[i:st)从而求出dfs(st)的解，只有任一分解成功，dfs(st)=true，否则false。

Cache的应用场景： 如果子问题重复就要用Cache。
例如dfs(10)=dfs(9)+s[9:9] = (dfs(8) + s[8:8]) + s[9:9]
=dfs(8)+s[8:9]
dfs(8)由第一层递归第二个循环s[8:9]和第二层递归s[9:9]达到，这是重复的子问题dfs(8)。如果不cache，dfs(8)的求解
是重复的。

Cache模板：

1. key为子问题索引st，value为子问题的解。
2. 紧跟终结条件，若在cache中，返回子问题的解。
3. 循环结束，将子问题的结果存于cache。

注意事项：

1. 将两个输入都转换成小写。
2. 递归中先查询词是否在字典中再递归。如果顺序调转就会LTE，因为这些子问题是白费的。
3. 递归终结条件为st==0而不是st==s.length()因为子问题递归从右到左。

Java代码：

public boolean wordBreakDFS(String s, List<String> wordDict) {
	if(s == null || s.isEmpty() || wordDict == null || wordDict.size() == 0)
		return false;
	Set<String> wordDictLower = new HashSet<>();
	for(String c : wordDict)
		wordDictLower.add(c.toLowerCase());
	s = s.toLowerCase();
	Map<Integer, Boolean> cache = new HashMap<>();
	return dfs(s, wordDictLower, s.length(), cache);
}

// subproblem's answer dfs[:st)
boolean dfs(String s, Set<String> wordDict, int st, Map<Integer, Boolean> cache) {
	if(st == 0)
		return true;
	if(cache.containsKey(st))
		return cache.get(st);
	boolean re = false;
	for(int i = 0; i < st; i++) {
		if(wordDict.contains(s.substring(i, st)) && dfs(s, wordDict, i, cache))
			return true;
	}
	cache.put(st, re);
	return false;
}

算法分析：

时间复杂度为O(n2)，空间复杂度为O(n)。