单词拆分

标签: 字典树 记忆化搜索 数组 哈希表 字符串 动态规划

难度: Medium

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

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

示例 1：

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

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示：

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s 和 wordDict[i] 仅由小写英文字母组成
  • wordDict 中的所有字符串 互不相同

Submission

运行时间: 17 ms

内存: 16.0 MB

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # 容量为len(s)的背包，物品为wordDict中的单词
        # 单词可重复使用，为完全背包问题
        # 1. dp[j]：物品能否达成容量为j的背包；j：长度
        # 2. 递推式：dp[j] = dp[j] or (dp[j - wordDict[i]] and s[j - wordDict[i] : j + 1] == wordDict[i])
        # 3. 初始化：dp[0] = True, dp[j] = False
        # 3. 遍历顺序：内外层背包物品均可，均需正序
        dp = [False] * (len(s) + 1)
        dp[0] = True
        for j in range(len(s) + 1):
            for i in range(len(wordDict)):
                if j >= len(wordDict[i]):
                    dp[j] = dp[j] or (dp[j - len(wordDict[i])] and s[j - len(wordDict[i]) : j] == wordDict[i])
        return dp[len(s)]

Explain

这个题解使用动态规划来解决单词拆分问题。它将问题转化为一个完全背包问题，其中背包的容量为字符串s的长度，物品为字典wordDict中的单词。dp[j]表示物品能否达成容量为j的背包。状态转移方程为：dp[j] = dp[j] or (dp[j - len(wordDict[i])] and s[j - len(wordDict[i]) : j] == wordDict[i])，即如果dp[j - len(wordDict[i])]为True，且s[j - len(wordDict[i]) : j]等于wordDict[i]，则dp[j]为True。最后返回dp[len(s)]即可得到结果。

时间复杂度: O(len(s) * len(wordDict))

空间复杂度: O(len(s))

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # 容量为len(s)的背包，物品为wordDict中的单词
        # 单词可重复使用，为完全背包问题
        # 1. dp[j]：物品能否达成容量为j的背包；j：长度
        # 2. 递推式：dp[j] = dp[j] or (dp[j - len(wordDict[i])] and s[j - len(wordDict[i]) : j] == wordDict[i])
        # 3. 初始化：dp[0] = True, dp[j] = False
        # 4. 遍历顺序：内外层背包物品均可，均需正序
        dp = [False] * (len(s) + 1)  # 初始化dp数组
        dp[0] = True  # 初始化dp[0]为True
        for j in range(len(s) + 1):  # 外层循环遍历背包容量
            for i in range(len(wordDict)):  # 内层循环遍历物品
                if j >= len(wordDict[i]):  # 如果当前背包容量大于等于当前物品的长度
                    # 状态转移方程
                    dp[j] = dp[j] or (dp[j - len(wordDict[i])] and s[j - len(wordDict[i]) : j] == wordDict[i])
        return dp[len(s)]  # 返回最终结果

Explore

在状态转移方程中，每次考虑的是从位置 `j - len(wordDict[i])` 到 `j` 的子字符串是否与 `wordDict[i]` 相匹配，且前一个状态 `dp[j - len(wordDict[i])]` 必须为真，即以 `j - len(wordDict[i])` 为结尾的字符串可以被 `wordDict` 中的其他单词分割。这种方法每次转移是基于之前已验证的子字符串，所以不会重复使用同一位置的字符，每个字符位置只被用来验证一次是否能形成有效的单词分割。

`dp[0]` 被设置为 `True` 是因为一个长度为0的字符串（空字符串）自然无需分割就是一个有效的分割。其他的 `dp[j]` 初始化为 `False` 表示在开始时，假设所有长度的字符串都不能被 `wordDict` 中的单词完全分割，这是一个安全的默认假设，只有当找到有效的单词匹配组合时才将对应的 `dp[j]` 更新为 `True`。

在传统的完全背包问题中，我们有一系列物品，每个物品可以被无限次选用，目标是填满一个给定的容量背包。在单词拆分问题中，字符串 `s` 的长度相当于背包的容量，而 `wordDict` 中的每个单词相当于背包问题中的一个物品。单词可以无限次使用来填充这个背包，即填充字符串 `s`。目标是完全使用 `wordDict` 中的单词填满整个字符串 `s` 的长度，不留空隙。

这种遍历顺序有助于确保在更新 `dp[j]` 值时，所有可能的单词长度和对应的子问题（即更小的 `j` 值）已经被考虑。这样可以保证在尝试填充任何长度为 `j` 的背包时，我们已经考虑了所有可能的单词组合来达到这个长度。此外，这种方法避免了在更新 `dp[j]` 时重复计算或遗漏任何单词的可能性，使得动态规划的表填充更为有效和系统。