LeetCode-139. 单词拆分【字典树 记忆化搜索 数组 哈希表 字符串 动态规划】

题目描述：

给你一个字符串 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 中的所有字符串 互不相同

解题思路一：Python动态规划五部曲：定推初遍举【先遍历背包 后遍历物品】必须是排列

【先遍历物品 后遍历背包】是组合，不可用

1. 确定dp数组以及下标的含义
   dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。

2. 确定递推公式
   如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。

所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

3. dp数组如何初始化
   从递推公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递推的根基，dp[0]一定要为true，否则递推下去后面都都是false了。

那么dp[0]有没有意义呢？

dp[0]表示如果字符串为空的话，说明出现在字典里。

但题目中说了“给定一个非空字符串 s” 所以测试数据中不会出现i为0的情况，那么dp[0]初始为true完全就是为了推导公式。

下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。

4. 确定遍历顺序
   题目中说是拆分为一个或多个在字典中出现的单词，所以这是完全背包。

还要讨论两层for循环的前后顺序。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

我在这里做一个总结：

求组合数：动态规划：518.零钱兑换II (opens new window)求排列数：动态规划：377. 组合总和 Ⅳ (opens new window)、动态规划：70. 爬楼梯进阶版（完全背包） (opens new window)求最小数：动态规划：322. 零钱兑换 (opens new window)、动态规划：279.完全平方数(opens new window)

而本题其实我们求的是排列数，为什么呢。 拿 s = “applepenapple”, wordDict = [“apple”, “pen”] 举例。

“apple”, “pen” 是物品，那么我们要求 物品的组合一定是 “apple” + “pen” + “apple” 才能组成 “applepenapple”。

“apple” + “apple” + “pen” 或者 “pen” + “apple” + “apple” 是不可以的，那么我们就是强调物品之间顺序。

所以说，本题一定是 先遍历 背包，再遍历物品。

5. 举例推导dp[i]
   以输入: s = “leetcode”, wordDict = [“leet”, “code”]为例，dp状态如图：
   

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

时间复杂度：O(n³)
空间复杂度：O(n)

解题思路二：Python动态规划版本二

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordSet = set(wordDict)
        n = len(s)
        dp = [False] * (n + 1)  # dp[i] 表示字符串的前 i 个字符是否可以被拆分成单词
        dp[0] = True  # 初始状态，空字符串可以被拆分成单词

        for i in range(1, n + 1): # 遍历背包
            for j in range(i): # 遍历单词
                if dp[j] and s[j:i] in wordSet:
                    dp[i] = True  # 如果 s[0:j] 可以被拆分成单词，并且 s[j:i] 在单词集合中存在，则 s[0:i] 可以被拆分成单词
                    break

        return dp[n]

时间复杂度：O(n³)
空间复杂度：O(n)

解题思路三：回溯

class Solution:
    def backtracking(self, s: str, wordSet: set[str], startIndex: int) -> bool:
        # 边界情况：已经遍历到字符串末尾，返回True
        if startIndex >= len(s):
            return True

        # 遍历所有可能的拆分位置
        for i in range(startIndex, len(s)):
            word = s[startIndex:i + 1]  # 截取子串
            if word in wordSet and self.backtracking(s, wordSet, i + 1):
                # 如果截取的子串在字典中，并且后续部分也可以被拆分成单词，返回True
                return True

        # 无法进行有效拆分，返回False
        return False

    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordSet = set(wordDict)  # 转换为哈希集合，提高查找效率
        return self.backtracking(s, wordSet, 0)

时间复杂度：O(n³)
空间复杂度：O(n²) # 递归