当前位置：首页 > news >正文

动态规划题解——单词拆分【LeetCode】

news 2025/7/15 9:20:44

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)@cachedef dfs(i:int)-> bool:if i == 0:return Truefor j in range(i-1, max(i-max_len-1, -1), -1):if s[j:i] in words and dfs(j):return Truereturn Falsereturn 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)，递归栈和缓存