139. 单词拆分

---

一、算法逻辑（逐步思路）

❓ 题目描述：

给定一个字符串 s 和一个单词字典 wordDict，判断是否可以将 s 拆分为若干个字典中的单词。

---

✅ 解题思路（自顶向下 DFS + 缓存）

1. 目标定义：

• 使用递归函数 dfs(i) 表示：s[:i] 是否可以合法拆分。

• • 比如：dfs(5) 表示 s[0:5] 能否由字典中的单词拼出。

2. 边界条件：

• dfs(0) = True，表示空字符串总是可以被拆分（“啥也不选”是合法的）。

3. 遍历决策：

• 每次从位置 i-1 向前遍历，尝试找一个单词 s[j:i] 满足：

• • s[j:i] in wordDict；
  • 且 dfs(j) 为真，即 s[0:j] 可拆分；

• 一旦找到一个合法的切割点 j，就返回 True；
• 如果尝试了所有切割点都失败，返回 False。

4. 剪枝优化：

• 用 max_len = max(len(w) for w in wordDict) 限制滑窗最大宽度，避免无效子串。

5. 记忆化搜索：

• 使用 @cache 缓存子问题结果，避免重复计算，提高效率。

---

二、算法核心点

✅ 核心思想：区间划分 + 记忆化搜索

• 本质是一个字符串划分问题，子问题是 s[:i] 能否拆分；
• 对每个位置 i，尝试所有可能的前缀切割；
• 每个子串 s[j:i] 都在尝试“是否能作为字典中一个词结尾”，并递归验证前缀 s[:j]；
• 使用缓存（记忆化）避免重复递归是性能提升关键。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        max_len = max(map(len, wordDict))
        words = set(wordDict)

        @cache
        def dfs(i:int)-> bool:
            if i == 0:
                return True
            for j in range(i-1, max(i-max_len-1, -1), -1):
                if s[j:i] in words and dfs(j):
                    return True
            return False
        return dfs(len(s))

---

三、复杂度分析

• 时间复杂度：O(n × L)

• • n = len(s)，L 为字典中最长单词的长度；
  • 每个位置最多尝试 L 次切分；
  • 总状态数为 O(n)，每个状态计算最多 O(L)，配合缓存只算一次。

• 空间复杂度：O(n)

• • 用于递归栈（最多深度 n）；
  • 缓存最多存 n 个状态。

---

总结表：

维度	内容
✅ 思路逻辑	从后向前切割字符串，判断是否可以用字典中单词组成
✅ 核心技巧	DFS + 记忆化搜索；利用 max_len 限制枚举范围，提高效率
✅ 时间复杂度	O(n × L)，n 是字符串长度，L 是最长单词长度
✅ 空间复杂度	O(n)，递归栈和缓存

---

💡 小拓展：

• 如果你想要得到所有可拆分方式，可以改写为返回列表；
• 如果你更倾向于迭代写法（DP 表），也可以用一维 dp[i] 表示 s[:i] 是否可拆分，时间复杂度类似。