139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

题解

主要分类：动态规划
思路：这题的要点在于如何使用动态规划。这是打死我也想不出来的方法。

1. 首先，我们要确定dp里面存储的是什么，建立dp[len(s)+1]， 为什么是len(s)+1， 因为它存储的是其前0-i-1能否利用worddict里面的词划分。因此，很容易想到其基础dp[0]=True
2. 那我们怎么确定前0-i-1是否能被其划分，状态如何转移。我们设置一个指针j, 让它依次遍历0-i-1检查是否存在一个位置使得0-j-1可以被划分，j-i-1也可以被划分，并且假设0-s1可以被划分s1-s2可以被划分那么0-s2也可以被划分，这样就不用去考虑其中有多少个单词，只需要知道它可以被划分就可以了。
3. 因此，我们可以建立状态转移方程： dp[i] = dp[j] and (s[j:i] in worddict)
4. 最后，return dp[len(s)+1]即可

例如：
s=applepenapple worddict=['pen', 'apple']
i = 1 a-> False
i = 2 p-> False
...
i = 5 当j=0的时候，满足要求， 因此dp[5]=True
...
i = 8 当j=5的时候，满足要求， 因此dp[8]=True
...
i=14, 当j=8的时候，满足要求， 因此dp[14]=True
最后返回True

代码如下：

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False for _ in range(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 wordDict)
                if dp[i]:
                    break
        return dp[len(dp)-1]