【DP】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 是否可以被空格拆分为一个或多个在字典中出现的单词。
注意： 字典中有可能有多余的单词。
想法1（贪婪算法，错误做法）：
- 使用两个索引 cur 和 nex 来遍历字符串，cur 指向当前字符，nex 每次向后移动一次；
- 判断 s[cur:nex] 是不是 wordDict 中的字符串。如果是，cur = nex 继续判断， 直到 cur 移动到字符串末尾，即 cur = len(s)；
- 如果最后一个子串 s[cur:nex] 在 wordDict 中，说明 s 可以被完全划分，返回 True，否则为 False。
当然，我们可以将 wordDict 转化为 dict 加速判断。实现代码如下：
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dic = dict()
for word in wordDict:
dic[word] = True
cur, nex = 0, 1
while nex != len(s):
if s[cur:nex] in dic:
cur = nex
nex += 1
if s[cur:nex] in dic:
return True
return False
但是，这样的想法是错误的！！！ 我们使用这种贪心策略，会忽略这样的问题。
s = "aaaaaaa"
wordDict = ["aaaa","aaa"]
我们相当于每次取最短，上述代码最后的划分结果就是 ["aaa", "aaa", "a"]，从而返回 False 的错误答案。
想法2（DP，正确做法）：
- 使用一个
dp = [True] + [False] * len(s)来标记字符串每个位置（相当于在每个字符串后加一个隔板）。dp[0] = True 是用来将字符串切出来的，dp[1] 到 dp[len(s)] 指向每个字符，初始化为 False。dp[i] 代表第 i 个位置是否可以划分。 - 遍历字符串每个位置，即
i = 1 to len(s) + 1，判断 s[i] 位置的 dp[i] 是否可以改写为 True。如果 s[i] 的位置可以划分，就要要求：
1、 以 s[i] 结尾的子串在这个字典里（我们可以遍历 wordDict，来查看是否s[i-len(word):i] == word）；
2、这个子串的前一个位置dp[i-len(word)]是 True 的状态。 - 最后，如果 dp[-1] 位 True，说明 s 可以被完全划分，否则为 False 代表不可以划分。
举例说明：
s = "catsandog", wordDict = ["cats", "cat", "and", "og", "aaa"]
首先 dp[0] = True；在遍历的过程中，dp[3] = True 因为以 t 结尾的 cat 在字典里面，且 dp[3-3] 为 True（这就是 dp[0] 为 True 的作用）；dp[4] = True 因为以 s 结尾的 cats 在字典里且 dp[4-4] 为 True；dp[7] 为 True 因为以 d 结尾的 and 在字典里且 dp[7-3] 为 True；dp[9] 为 True 因为以 g 结尾的 og 在字典里且 dp[9-2] 为 True；最后，dp[-1] = dp[9] = True，得到划分结果 ['cats', 'and', 'og']。
其实，可以发现 s[i] = True 将字符串划分为两部分，s[0:i] 为可以在字典中划分的，s[i:] 为待划分的字符串。
时间复杂度为 O(N*M)，空间复杂度 O(N)，其中 N 为字符串长度，M 为字典中 word 个数。
Python3 实现：
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [True] + [False] * len(s)
for i in range(1, len(s) + 1):
for word in wordDict:
if i >= len(word) and dp[i-len(word)] and word == s[i-len(word):i]:
dp[i] = True
return dp[-1]
