139. 单词拆分（中等）-动态规划

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用

分析

• 遍历的不一定是列表，也可以是索引
• 方案二是使用动态规划

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # 遍历的不一定是列表，可以是字符串的位置
        wordDict = set(wordDict)
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True

        for i in range(1, n+1):
            for j in range(i):
                # dp[j]代表前j个字符组成字符串的状态，s[j:i]代表j+1个字符（包含）到i个字符（包含）字符串
                # 这个下标要特别注意
                # 也是寻找满足一下两个条件的
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    # 找到就可以判断，可以break出来
                    break
        
        return dp[-1]

方案二

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # 动态规划更简单
        # s按照字母来遍历，判断是否能拼出分两部分，dp[j]和s[j:i]是否在word set中

        word_set = set(wordDict)
        n = len(s)

        dp = [False]*(n+1)
        dp[0] = True
        for i in range(1, n+1):
            # 注意索引i可以想象成字母个数
            # j可以想象成第几个字母，dp[j]其实应该是j个字母的结果，s[j:i]是从j+1个字母开始算的
            for j in range(i):
                if dp[j] and s[j:i]  in word_set:
                    dp[i] = True
                   
                    break

        return dp[n]