LeetCode 139. 单词拆分

题目

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

例：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

方法：动态规划

本题为完全背包，因为字典中的单词可以重复使用

• dp[j] 表示长度为 j 的字符串是否可以拆分成 wordDict 中的单词，初始化为 False
• 因为 dp[0] 为之后的 dp[j] 的基础，所以应为 True，否则之后所有的 dp[j] 均为 False
• 外层循环为对字符串（背包容量）的正序循环，内层循环为对字典 wordDict （物品）的正序循环
• 递推公式：若此时字符串的长度大于单词的长度，即该单词可能为该字符串的一部分，那么该字符串是否可以由字典中的单词拼接成有两种可选方式。一种为原 dp[j]，即之前过程中判断的该字符串是否可以由单词组成；另一种为，当未放入同单词长度相等的字符串前的字符串可以由字典中的单词组成，并且该同单词长度相等的字符串可以由字典中的单词组成时，dp[j] 为 True

class Solution(object):
    def wordBreak(self, s, wordDict):
        dp = [False] * (len(s) + 1)
        dp[0] = True
        for j in range(1, len(s) + 1):
            for word in wordDict:
                if j >= len(word):
                    dp[j] = dp[j] or (dp[j-len(word)] and s[j-len(word): j] == word)
        return dp[len(s)]

参考

代码相关：https://programmercarl.com/0139.%E5%8D%95%E8%AF%8D%E6%8B%86%E5%88%86.html