这道题在力扣热题100里排在第82位，是动态规划专题里非常经典的一道入门题。很多人第一次看到“单词拆分”这个标题，会觉得是要处理什么天然的文本分割问题，但实际上它考察的就是一个很朴素的思路：一个字符串能不能被拆成若干个字典里出现过的单词。题目本身不长，但解法背后的思路延展性很强，刷透这一题，动态规划的“状态设计”这一课基本就算补上了。
这类题目在面试里出现频率也高，尤其是偏算法岗的现场面，因为它在暴力递归、记忆化搜索、动态规划、广搜、甚至字典树优化这几个层级上都能做文章，非常适合考察候选人从朴素解法到最优解法的推导能力。这篇文章我打算把这道题从题目理解、状态设计、代码实现到各种优化思路完整过一遍，顺便把我在提交过程中踩过的坑和排查经验也整理出来。不管你是刚开始刷热题100，还是复习动态规划想找一道题打通思路，这篇都对你胃口。
1. 题目理解与核心思路拆解
先看题面。给你一个字符串s和一个单词字典wordDict，判断s是否可以被拆分成一个或多个字典中出现的单词，拆的时候单词可以重复使用。例如s = "leetcode"，字典["leet", "code"]，返回true，因为可以拆成"leet"和"code"。
1.1 这个题到底在问什么
把题目翻译成人话：给你一把长度固定的积木（字典里的单词），你能不能正好用这些积木拼出目标图形（字符串s）？积木可以重复用，拼的时候必须每一段都刚好是字典里的某个词，不能有残留，也不能超出长度。
这里有几个关键点容易被忽略，我先拎出来：
- 字典里的单词在判断时是可重复使用的，所以它不是背包问题里那种每个物品只能用一次的限制，反而是完全背包的语境。
- 拆分出来的每个片段必须是字典中出现的单词，也就是说我们要对
s做切割，切割点可以任意选，但切出来的每一段都要能在字典里找到。 - 不需要输出具体怎么拆，只需要判断能不能拆。所以这个题本质上是一个可行性问题，而不是方案计数或方案输出问题。
正是最后这一点，决定了它最适合用动态规划来做。你要做的是把一个大问题分解成互相重叠的子问题，然后每个子问题只记录一个布尔值：这个前缀能不能拆。
1.2 为什么暴力回溯会超时
刷题第一步要养成习惯：先用最朴素的思路想通，再考虑怎么优化。单词拆分的朴素思路是回溯，即从字符串开头出发，枚举所有可能的单词作为第一段，如果匹配上，就递归检查剩余部分。
这么说起来似乎可行，实际一写代码就会发现灾难。以s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"，字典为["a", "aa", "aaa", "aaaa", "aaaaa"]这种输入为例，递归树以指数级膨胀，大部分路径都在重复计算同一个后缀能不能拆。更致命的是，如果不存在可行拆法，回溯会遍历近乎所有组合才会终止，直接原地爆炸。
所以这类“大问题能否拆成子问题且子问题有重叠”的迹象一出现，第一反应就应该是动态规划。
1.3 动态规划是这道题的唯一正解吗
可以明确地回答：对这道题来说，动态规划（包括它的记忆化搜索变体）就是最标准的解法。LeetCode官方题解的主流出路也是动态规划。不仅如此，这道题还有两个有趣的变体视角：
- 把字符位置看作图中的节点，如果
s[j:i]是字典中的单词，就存在一条从j到i的边。问题转化成了从节点0能否到达节点n，于是可以用BFS求解。 - 如果把字典建成字典树
Trie，可以在内层循环中利用前缀树加速匹配，避免对每个j都做一遍子串提取和哈希查找。
这两种视角各有适用场景，稍后我会展开讲。但无论哪个视角，底层状态设计的逻辑都逃不开动态规划那一套核心思想。所以先吃透动态规划，其他都是锦上添花。
2. 动态规划状态设计与转移方程推导
这一节是整道题的关键，也是面试官最愿意深挖的地方。如果状态定义说清楚了，转移方程写不出来都是扣分；如果转移方程写出来了但不知道为什么要这么设计，面试追问几轮就会露馅。
2.1 状态定义：dp[i]到底表示什么
定义dp[i]表示字符串s的前i个字符（即子串s[0:i]）能否被字典中的单词拆分，能则为True，不能则为False。
这里一定要建立索引对应的概念。很多初学者在这里容易搞混：dp[i]对应的不是字符s[i]，而是从开头数起的前i个字符。比如s = "leetcode"，那么：
dp[0] = True，表示空前缀天然可以拆分。dp[1]对应"l"这个前缀能否拆分。dp[4]对应"leet"能否拆分。dp[8]对应"leetcode"能否拆分。
最终答案就是dp[n]，其中n = len(s)。
2.2 状态转移方程的直观推导
假设我们已经知道了所有dp[0]到dp[i-1]的值，现在要算dp[i]。应该怎么思考？
只需要做一件事：枚举最后一个单词的起始位置j。如果s[j:i]这个子串在字典里，并且dp[j] == True（也就是说j位置之前的部分能拆成合法单词），那么把两个部分拼起来，s[0:i]就一定能拆。于是：
dp[i] = True 当且仅当存在一个 j (0 <= j < i)，使得 dp[j] == True 且 s[j:i] in wordDict如果不存在这样的j，dp[i]就是False。
这个转移方程的巧妙之处在于，它把“前i个字符能不能拆”这个大问题，转化成了“前j个字符能不能拆”这个更小的子问题，再加上一次O(1)的哈希查找。子问题的规模逐步缩小，最终落在dp[0] = True这个已知的初始条件上，形成完整的递推链。
2.3 枚举顺序与复杂度估计
双层循环的结构几乎是确定的：外层循环枚举i从1到n，内层循环枚举j从0到i-1。每个i都要扫描它前面所有可能的分割点。
时间复杂度最直接的分析是O(n^2)次子串判断，每次判断是一个字符串切片加哈希查找。Python里切片本身是O(k)的复制操作（k为切片长度），所以严格意义上总复杂度是O(n^3)。但工程上因为k通常远小于n，实际表现不会那么差，一般官方题解的复杂度分析也按O(n^2)来定性描述，LeetCode的测试数据下这个写法的运行时间是可接受的。
空间复杂度是O(n)，只用一个一维数组存布尔值。这个开销在所有动态规划题目里算非常轻的了。
2.4 为什么dp[0]必须是True
dp[0]代表空前缀，它不是真实存在的字符串片段，但它是整个递推的基石。如果不把它设为True，那么当某个单词s[0:i]本身就在字典里时，dp[i]永远不会被标记为True，因为dp[0]是False，就算子串匹配成功也满足不了dp[j] == True的条件。
空串能不能拆？这道题的语义里不关心这个问题，它只是一个为了让转移方程自洽的辅助值。面试时被问到直接回答“它是初始条件，用来表示字符串起点之前的空状态可以被视为已拆分即可”，不要支支吾吾。
3. 核心解法实现与代码详解
理论讲完，直接上代码。我以Python为例写一版最接近标准动态规划思路的实现，然后逐行讲清楚每个细节。
def wordBreak(s: str, wordDict: list[str]) -> bool: # 把字典转成哈希集合，查找效率O(1) word_set = set(wordDict) n = len(s) # dp[i] 表示 s[0:i] 能否被拆分 dp = [False] * (n + 1) dp[0] = True for i in range(1, n + 1): for j in range(i): # 如果前缀 s[0:j] 能拆分，且 s[j:i] 在字典中 if dp[j] and s[j:i] in word_set: dp[i] = True # 只要找到一个合法拆法，当前 i 就可以提前结束 break return dp[n]3.1 逐行拆解：为什么要这么做
第一处值得注意的细节是word_set = set(wordDict)。这一步很多人会漏，直接拿wordDict这个列表去判断s[j:i] in wordDict。列表的in操作是线性扫描，最坏情况O(k)，其中k是字典长度。套在双层循环里，整体复杂度直接再乘一个k，部分测试用例会因此超时。转成哈希集合后，判断一个单词是否存在的均摊复杂度降为O(1)，这是整个优化链条里最基础也是性价比最高的一步。
第二处是dp = [False] * (n + 1)。数组长度是n + 1而不是n，因为dp索引对应的是前缀长度，从0到n共n + 1个状态。漏掉dp[0]或者忘了初始化它，都会让答案出错。
第三处是break。内层循环只要找到一个j满足条件，dp[i]就已经是True了，后面再枚举更大的j没有意义。这个break对整体性能的贡献在极端情况下非常可观，比如"aaaaaaaaaaaaab"这种失败场景，它不能早停；但如果是"leetcode"这种很快命中的场景，它能在第一个合法分割点处就收工。这一步属于白送的性能优化，不加白不加。
3.2 边界条件推演：手动跑一个完整例子
拿s = "leetcode"，wordDict = ["leet", "code"]走一遍流程：
- 初始化：
dp[0] = True，其余为False。 i = 1，子串s[0:1] = "l"不在字典，dp[1] = False。i = 2，考察s[0:2] = "le"不在字典，dp[2] = False。i = 3，s[0:3] = "lee"不在字典，dp[3] = False。i = 4，j = 0时s[0:4] = "leet"在字典且dp[0] = True，所以dp[4] = True，break。i = 5，j从0到4依次尝试，s[0:5] "leetc"、s[1:5] "eetc"均不在字典……直到j = 5结束，没找到，dp[5] = False。i = 6，类似，所有候选子串都不在字典，dp[6] = False。i = 7，都失败，dp[7] = False。i = 8，j = 0时s[0:8] = "leetcode"不在字典；j = 4时dp[4] = True且s[4:8] = "code"在字典，于是dp[8] = True。
最终dp[8] = True，输出正确。
这个推演过程建议大家自己在纸上画一遍，画完就理解了为什么dp[i]只关心“能否”，而不关心“怎么拆”——中间怎么拆的细节在状态里已经被丢掉了，只留下一个布尔值继续向上传递。
3.3 复杂度的工程视角分析
理论复制度上面已经说过了，这里补充一点工程视角的观察。LeetCode上有一些刻意构造的极端用例，比如字典中大量超短单词、目标串巨长且由相同字符重复组成。在这种输入下，内层循环会跑满，实际耗时可能到数百毫秒。在本地调试时如果用Python跑极端用例，建议开启PyPy或C++重写来验证性能差异，语言层面的常数差距在这种O(n^2)级别的算法上会被放大。
4. 常见问题与排查技巧实录
这道题刷的人多，踩坑记录也丰富。我把提交过程中最常见的几类问题和对应的排查思路整理成一个速查表，方便你对照自查。
| 问题现象 | 可能原因 | 排查与解决方案 |
|---|---|---|
| 提交超时，本地简单样例正常 | 内层循环没有break，或字典没转哈希集合 | 增加break，确认用的是set而非list |
小规模样例输出False但预期True | 忘记初始化dp[0] = True | 检查初始化逻辑，dp[0]永远是递推基石 |
| 结果不稳定的随机错误 | 切片索引越界或j从1开始枚举 | 写出dp数组推演一个小样例，确认j从0开始 |
| 答案差一位的边界错误 | dp[i]与s[i]混淆，索引理解偏差 | 回到定义，画一遍dp数组和字符串下标的对应关系 |
| 内存占用偏高 | 尝试了二维dp或存储了所有拆分方案 | 本题只需一维布尔数组，二维纯属多余 |
| 使用递归记忆化但爆栈 | 递归深度接近字符串长度 | 改为迭代式动态规划，彻底避免栈溢出风险 |
4.1 经典错误：字典是列表导致超时
这是我最早刷这道题的真实经历。第一次提交时很自信，把wordDict原封不动用于判断，结果一个中等规模测试用例就超时了。当时还没意识到列表in和集合in的性能差距有多大，后来把wordDict转成set再提交，运行时间从超时降到了几十毫秒。
这个坑在真实业务里也有对应场景：数据量一大，查找数据结构的选择直接决定接口能不能扛住压力。刷题时养成“查找先转哈希”的习惯，对工作里的代码评审也很有帮助。
4.2 经典错误：break丢了导致性能退化
再看一个典型代码：
for i in range(1, n + 1): for j in range(i): if dp[j] and s[j:i] in word_set: dp[i] = True # 没有 break，continue 继续跑剩下的 j没有break的情况下，比如"catcatcat"这种一旦j = 0命中就得停的场景，代码还会继续扫描j = 1到j = i - 1，白白做了大量无效子串判断。在n = 300、字典很小的情况下，这个差异可能只有几毫秒，但输入长度上千以后，差别会被放大。
从代码规范的角度说，找到答案后立即退出是一个通用原则。动态规划里只要当前状态已经被确定为True，后续枚举只会浪费算力。
4.3 更隐蔽的坑：用切片判断时的字符串复制开销
Python里s[j:i]是一次子串复制，会额外占用内存。在双层循环里，这个复制次数是O(n^2)量级的，虽然单次复制长度有限，但累计开销不容忽视。想进一步优化可以改用startswith方法，或者直接对s[j:]调用startswith判断前缀单词，从数据结构层面减少复制。写一个优化版：
def wordBreak_optimized(s: str, wordDict: list[str]) -> bool: word_set = set(wordDict) n = len(s) dp = [False] * (n + 1) dp[0] = True for i in range(1, n + 1): for w in word_set: lw = len(w) if i >= lw and dp[i - lw] and s[i - lw:i] == w: dp[i] = True break return dp[n]这个版本的思路反过来：不再枚举分割位置j，而是枚举字典中的每个单词，看它能否刚好接在某个可拆分前缀的末尾。它的好处是循环次数和字典大小相关，如果字典很小而字符串很长，这个版本效率明显更高。但要注意，它依赖于len(w)精确匹配，如果字典里有很多相同长度的词，依然要逐一尝试。
4.4 记忆化搜索与动态规划：同一种思路的两种写法
除了自底向上的迭代式动态规划，自顶向下的递归加记忆化也能解决这道题。核心思路是定义递归函数dfs(i)表示s[0:i]能否拆分，然后枚举分割点，遇到已计算的状态直接返回缓存结果。
from functools import lru_cache def wordBreak_memo(s: str, wordDict: list[str]) -> bool: word_set = set(wordDict) n = len(s) @lru_cache(None) def dfs(i): if i == 0: return True for j in range(i): if dfs(j) and s[j:i] in word_set: return True return False return dfs(n)递归写法在思路上更接近人类直觉——“前i个字符能不能拆，取决于前面某个j能不能拆加上最后一段在不在字典里”。代价是有递归调用开销和栈溢出的风险（尽管对这道题的长度而言风险不大）。迭代式动态规划没有这个问题，所以我个人推荐以迭代式为主、递归式用于理解思路。面试时如果被问到两种写法的区别，能说出“递归适合描述状态、迭代适合实际执行”就算过关。
4.5 最长单词长度剪枝：一个容易被忽略的小优化
在枚举分割点j时，j越小，s[j:i]越长。而字典中的单词长度通常远小于字符串长度，因此我们可以提前记录字典中单词的最大长度max_len。枚举分割点时，如果i - j > max_len，说明当前子串长度已经超过字典中任何单词的长度，s[j:i]必然不在字典中，直接跳过。这个剪枝能把内层循环从O(i)降到O(max_len)，当字典里单词普遍较短时效果明显。
def wordBreak_with_pruning(s: str, wordDict: list[str]) -> bool: word_set = set(wordDict) max_len = max(len(w) for w in wordDict) n = len(s) dp = [False] * (n + 1) dp[0] = True for i in range(1, n + 1): # 只枚举可能作为分割点的 j for j in range(max(0, i - max_len), i): if dp[j] and s[j:i] in word_set: dp[i] = True break return dp[n]注意这里j的范围变成了[max(0, i - max_len), i)，意思是最远的前缀长度不能短到让剩余部分超过max_len。这是一个数学上严格成立的剪枝，不改变结果，只缩小搜索空间。我在实际提交中，这个版本在长字符串用例下的运行时间是最短的。
5. 题目变形与面试延伸
刷题不能只满足于过掉一道题，要有意识地把它放到更大的知识网络里看。单词拆分这题和好几个经典题都有联系，面试官也喜欢在这附近追问。
5.1 从动态规划视角看，这题和完全背包什么关系
如果将字典中的单词看作物品，字符串s看作背包容量，那么每个单词可以重复使用，且我们需要恰好填满背包。这对应的是完全背包的判定问题。完全背包的经典转移是dp[i] |= dp[i - weight[j]]，这题里weight[j]换成了单词长度，dp[i] |= dp[i - len(w)]且要求对应子串匹配。想通这层联系，你就把“单词拆分”和背包问题统一到了一个知识框架里，遇到类似的字符串拼接判定题就能举一反三。
5.2 从图论视角看，这题等价于路径可达
把字符串的每个前缀位置抽象成图的节点（0到n一共n+1个节点），如果s[j:i]在字典中，就添加一条从节点j到节点i的有向边。那么题目要回答的就是：是否存在一条从节点0到节点n的路径。这是一个标准的有向图可达性问题，可以用BFS求解：
def wordBreak_bfs(s: str, wordDict: list[str]) -> bool: word_set = set(wordDict) n = len(s) visited = [False] * (n + 1) queue = [0] while queue: start = queue.pop(0) if start == n: return True for end in range(start + 1, n + 1): if not visited[end] and s[start:end] in word_set: visited[end] = True queue.append(end) return FalseBFS的复杂度依然是O(n^2)，但好处是不需要完整计算所有dp[i]，找到一个合法路径就提前结束。在“能拆就立刻返回”的场景下，BFS通常比动态规划更快。面试时如果先写BFS再被追问动态规划写法，反而能展示你对同一问题的多角度理解。
5.3 相关进阶题：单词拆分II与拼接方案输出
一道经典的追问是：如果不仅要判断能否拆分，还要输出所有可能的拆分方案（LeetCode 140题），该怎么处理？
方案输出意味着我们不能再只保留布尔值，必须记录每个dp[i]是由哪些前置状态j转移来的。有两种常见做法：
- 在动态规划的过程中用一个
pre[i]列表记录所有能使dp[i]为True的j，最后从n回溯拼接出所有方案。 - 直接用带记忆化的深度优先搜索，从末尾往前找分割点，递归收集所有组合。
这两条路径都要在“单词拆分”的基础上增加一个维度——从判断是否存在变为穷举所有合法路径。复杂度也相应从O(n^2)上升到指数级，因为方案数本身就可能是指数级的。
5.4 字典树优化：当字典很大时怎么加速匹配
如果wordDict非常大，大到哈希集合的内存都不太友好，或者字符串长度很长，用字典树（Trie）来加速前缀匹配会是一个精巧的优化方向。核心思路是在内层循环中，不枚举所有j，而是从当前位置i往前，在Trie中逆向匹配字符，一旦匹配失败立即停止。这样每个i的匹配开销从O(n)降到O(max_word_len)，而且不需要做子串切片。
不过说实话，这道题在面试中要求手写Trie优化的概率不高，更多是作为扩展知识点被提及。了解思路即可，重点还是把基础动态规划写熟。
6. 实操总结与个人经验
刷这道题我前后写过三个版本。第一个版本用列表判断字典，提交超时；第二个版本改成哈希集合加break，正常通过；第三个版本加了最长单词长度剪枝，在极端长字符串用例上耗时又降了一截。整个过程帮我加深了一个习惯：先优化数据结构，再优化算法流程，最后再考虑算法层面的大改。
单词拆分这道题在我看来是动态规划入门的“标准样板间”。状态定义清晰（一维布尔数组），转移方程直观（枚举分割点拼接判断），初始条件明确（dp[0] = True），优化方向多样（剪枝、BFS、字典树）。把这题吃透，后面做编辑距离、最长递增子序列、背包问题时会顺很多，因为你会慢慢发现，所有动态规划题目其实都在做同一件事：用状态记录子问题的答案，再用转移把子问题的答案拼成大问题的答案。
最后分享一个小技巧：这题写完以后，不要急着看题解。自己把dp数组打出来，用"leetcode"和"leet", "code"这类小用例手动走一遍，再换一个拆分失败的用例走一遍。这一步走完，你对动态规划的“自底向上”四个字会有完全不一样的感觉。
