0139. 单词拆分
题目描述
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s。
注意： 不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例
示例 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
解题思路
第一步：理解问题
判断字符串 s 能否被完全拆分成字典中的单词。这是一个完全背包 / 分割型 DP 问题。
第二步：暴力解法 - 回溯
从位置 0 开始，枚举所有可能的结束位置，如果子串在字典中，就递归检查剩余部分。
def wordBreak(s, wordDict):
word_set = set(wordDict)
# dfs(start) 表示 s[start:] 这一段能否被完整拆开
def dfs(start):
# 已经走到串尾，说明前面的切分全部命中，成功
if start == len(s):
return True
# 枚举这一刀切在哪里：end 是开区间右端，所以取到 len(s)
for end in range(start + 1, len(s) + 1):
# 当前这一段在字典里，且剩下的部分也能拆开，就成功
if s[start:end] in word_set and dfs(end):
return True
# 所有切法都不行
return False
return dfs(0)
没有剪枝时会超时，因为同一个位置可能被重复计算很多次。
第三步：优化 - 记忆化搜索
用 lru_cache 或数组记录每个位置是否可拆分，避免重复计算：
from functools import lru_cache
def wordBreak(s, wordDict):
word_set = set(wordDict)
# 同一个 start 会从不同切分路径重复到达，缓存后只算一次
@lru_cache
def dfs(start):
if start == len(s):
return True
# 从 start 往后逐字符扩出一个候选词，逐个试
for end in range(start + 1, len(s) + 1):
if s[start:end] in word_set and dfs(end):
return True
return False
return dfs(0)
第四步：最优解法 - 动态规划
设 dp[i] 表示 s[0:i]（前 i 个字符）是否可以被拆分。
状态转移：
dp[i] = any(dp[j] and s[j:i] in word_set for j in range(i))
def wordBreak(s, wordDict):
word_set = set(wordDict)
# dp[i] 表示前缀 s[:i] 能否被完整拆开，长度 n+1 覆盖空前缀
dp = [False] * (len(s) + 1)
# 空前缀不需要任何单词，作为递推的起点
dp[0] = True
for i in range(1, len(s) + 1):
# 枚举最后一段的起点 j：s[:j] 能拆开，且 s[j:i] 是字典词
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[len(s)]
时间复杂度：O(n²)，空间复杂度：O(n)。
完整代码实现
算法可视化 · 逐帧回放这道题的代码5 帧 · 录制输入 "catsandog", ["cats", "dog", "sand", "and", "cat"]
from typing import List
from functools import lru_cache
class Solution:
"""
139. 单词拆分 - 记忆化搜索
核心思想：
从位置 k 开始枚举所有结束位置，如果子串在字典中，递归检查剩余部分。
使用 lru_cache 避免重复计算同一位置的结果。
时间复杂度：O(m²)
空间复杂度：O(m)
"""
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
# 字符剪枝：s 里出现过的字符，字典里至少得有一个单词含它。
#
# 只能比**集合**，不能比次数 —— 单词可以重复使用，
# "applepenapple" 用 apple + pen + apple 拆得开，
# 而 apple + pen 里只有 1 个 a，比次数会把它误判成无解。
dict_chars = set()
for word in wordDict:
dict_chars.update(word)
if set(s) - dict_chars:
return False
m = len(s)
word_set = set(wordDict)
ans = False
@lru_cache(maxsize=None)
def dfs(k: int):
nonlocal ans
if k == m:
ans = True
return
if ans:
return
path = ""
for i in range(k, m):
path += s[i]
if path in word_set:
dfs(i + 1)
if ans:
return
dfs(0)
return ans
示例推演
以 s = "leetcode", wordDict = ["leet", "code"] 为例。
dfs(0)：从位置 0 开始
- i = 0~3，path =
"leet"，在字典中，进入 dfs(4)- i = 4~7，path =
"code"，在字典中，进入 dfs(8)- k == 8 == m，ans = True，返回
- i = 4~7，path =
最终答案：True
以 s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 为例：
dfs(0)：
"cats"在字典中，进入 dfs(4)"and"在字典中，进入 dfs(7)"og"不在字典中，"dog"需要s[7:10]，但字符串只剩 2 个字符- 没有可选路径，返回 False
"sand"在字典中，进入 dfs(8)- 只剩
"og"，不在字典中
- 只剩
"cat"在字典中，类似的分析也会发现无法完全匹配
最终答案：False
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力回溯 | O(2^n) | O(n) | 无记忆化会超时 |
| 记忆化搜索 | O(n²) | O(n) | 避免重复计算 |
| 动态规划 | O(n²) | O(n) | 最优解 |
易错点总结
1. 字符剪枝只能比集合，不能比次数
直觉上会想「s 里字符的出现次数超过字典里能凑出的次数就无解」—— 但字典里的单词可以重复使用，这个推断不成立。
"applepenapple" 用 apple + pen + apple 拆得开，而 apple + pen 里只有 1 个 a；
按次数剪枝会提前 return False，把有解的输入判成无解（题面示例 2 就是这种）。
要剪就只能比集合：set(s) - 所有单词用到的字符集合，非空才无解。
2. lru_cache 的清零
如果同一个 Solution 实例被多次调用，Python 的 @lru_cache 基于函数对象，会被复用。在测试中最好每次新建实例。
3. DP 的初始状态
dp[0] = True 表示空字符串总是可以被拆分（作为基准状态）。
扩展思考
如果要求输出所有拆分方案？
就是 140. 单词拆分 II，需要在回溯时记录路径。
如果字典中的单词只能用一次？
那就变成了排列组合问题，需要用状态压缩 DP。