day46| 139

139. 单词拆分

题目简述：

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

1. 初始化dp=[False,......,False]，长度为n+1

2. dp[i]表示s的前i位是否可以用wordDict中的单词表示

3. 初始化dp[0]=True，空字符可以被表示

4. 遍历字符串的所有子串，遍历开始索引i，遍历区间[0,n)

　　遍历结束索引 j ，遍历区间[i+1,n+1):

　　　　若dp[i]=True且s[i,...,j)在wordDict中，则dp[j]=True

代码如下：

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