1. 题目本体先搞清楚单词拆分到底在问什么刷LeetCode的人应该都有这种感觉有些题一看就有思路有些题看完了连它在问什么都得琢磨半天。139题属于后者里比较典型的一道因为它披着字符串的外衣其实内核是动态规划而且题干本身很短反而容易让人轻视。先看一下原题描述给定一个非空字符串 s 和一个包含非空单词的字典 wordDict判定 s 是否可以被空格拆分成一个或多个字典中出现的单词。注意拆分的时候字典中的单词可以重复使用不要求全部用完。举个例子s leetcodewordDict [leet, code]因为可以拆成leet code所以返回 true。再看一个典型的 false 例子s catsandogwordDict [cats, dog, sand, and, cat]。这里就非常有意思了catsandog可以切出cats and og但og不在字典里或者cat sand og还是卡在og上。也就是说前面的部分怎么切都能切通但最后剩下的尾巴接不上整体就是 false。这道题在LeetCode上的编号是139属于动态规划专题里的高频题在字节、腾讯、微软的面试题单里出场率都不低。它适合什么人刷我觉得有三类人最应该认真对待一是刚开始接触动态规划、想找一道不那么数学的DP题入手的同学二是准备面试、需要快速复习字符串类DP套路的人三是想搞明白记忆化搜索和自底向上DP两种写法到底有什么区别的进阶选手。很多人第一次看到这题第一反应是用回溯或者暴力枚举把字符串切成所有可能的子串组合然后逐个检查是否在字典里。思路本身没错但问题在于字符串长度为 n 时所有可能的切分方式是指数级的n20 的时候还行n100 的时候直接爆炸。这道题真正要考察的是你能不能意识到大量子问题被重复计算然后用动态规划或记忆化搜索把复杂度降下来。在往下拆解法之前先澄清一个很多新手会搞混的点这里的拆分不是要求你把所有可能的拆分方案都列出来它只问你能不能拆。所以解题思路的核心不是枚举所有切法而是判断是否存在一种切法。判断存在性天然就比枚举全部方案省力气这也是DP能派上用场的根本原因。2. 为什么暴力回溯不行先算清楚复杂度账先说暴力解法的问题这样你才能理解后面DP优化到底优化了什么。假设字符串长度为 n每次递归处理前缀时我们需要枚举下一个单词的结束位置也就是从当前位置开始依次尝试长度为 1 到 n-i 的子串。最坏情况下每一步都可能产生多个分支递归树的节点数会接近 2 的 n 次方。如果你的字典里恰好包含了所有可能的子串那么每个节点都会分裂成多个子节点实际跑起来会非常恐怖。我见过有人拿回溯法硬解这题在小规模测试样例上确实能过但一提交就超时。原因很简单LeetCode的测试用例里藏着长度超过100的字符串而且字典设计得很有心机大量的连续字母会导致重复子问题爆炸。这里有个关键观察假设你递归地检查了从下标 i 开始的子串是否能被拆分这个结果其实和你怎么到达下标 i 的完全无关。也就是说s.substring(i) 的拆分可行性是固定的不管你是从 i-1 切过来的还是从 i-3 切过来的只要到了 i 这个位置后面的结果都一样。这就造成了大量的重复计算。比如 s aaaaaaaaabwordDict [a, aa, aaa, aaaa, aaaaa]递归过程中从下标 5 开始的子串能被拆分吗这个问题会被计算很多次因为你可以通过很多不同的前缀组合到达下标 5。每次重新计算一遍纯属浪费。动态规划解决的就是这个问题把每个位置的结果存下来算过一次就直接查表。记忆化搜索是加备忘录的自顶向下标准DP是自底向上的填表核心思想一模一样只是代码风格不同。这也是为什么我在刷题的时候经常说看到存在性问题重复子问题无后效性优先考虑DP不要一根筋走回溯。3. 核心思路拆解状态定义和转移方程的由来先看状态定义。定义一个布尔数组 dp其中 dp[i] 表示字符串 s 的前 i 个字符也就是 s.substring(0, i)能否被拆分成字典中的单词。注意这里的下标含义我见过不少人因为下标搞混把状态定义成s 的前 i 个字符能否拆分但在写循环的时候又把 i 当成字符下标直接用结果边界全乱这种细节在面试现场很致命。为什么状态要定义成前 i 个字符而不是到下标 i 为止因为 substring 的结束位置是开区间。dp[0] 表示空串是边界条件值为 true因为空串可以被认为是不需要拆分就满足条件的。这个初始值是整个转移方程能跑起来的前提千万别漏。再看状态转移。我们要判断 dp[i] 是不是 true本质上是问能不能找到一个位置 jj 从 0 到 i-1使得 dp[j] 为 true 且 s.substring(j, i) 在字典里。如果存在这样的 j那么 dp[i] 就为 true。写成数学形式就是dp[i] OR over j in [0, i-1] of (dp[j] wordDict.contains(s.substring(j, i)))。为什么是这个形式想一下拆分的物理意义前 i 个字符要能拆开必然是前 j 个字符已经拆好了 第 j 到 i 个字符恰好构成一个字典词。这个 j 就是最后一刀切的位置。我们不需要关心前 j 个字符具体是怎么拆的那是 dp[j] 已经回答过的问题。这就是无后效性的体现dp[j] 一旦算出来后面的推导只需要它的值不需要回溯中间过程。举个例子s leetcodewordDict [leet, code]。dp[0] true。计算 dp[4] 时j 从 0 到 3 遍历j0 时 dp[0] 为 trues.substring(0, 4) leet在字典里所以 dp[4] true。这意味着前4个字符leet可以被拆分。接着算 dp[8] 时j4 时 dp[4] 为 trues.substring(4, 8) code在字典里所以 dp[8] true。答案就是 dp[8]。这里面有个隐含细节dp[i] 是否只需要一个 j 达到条件就够了是的因为题目只问能不能拆不是问有多少种拆法。所以一旦发现某个 j 满足条件就可以提前跳出内层循环不用把 j 全遍历完。这个优化虽然不改变最坏复杂度但在用例设计的比较友好的情况下能省不少时间。4. 两种主流实现记忆化搜索和自底向上DP先写自底向上DP的实现。这个版本比较好理解代码也很短是面试中最推荐先写出来的方案。def wordBreak(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 j in range(i): if dp[j] and s[j:i] in word_set: dp[i] True break return dp[n]这里有个优化点wordDict 转成 set把查找从 O(k)k为字典大小降到 O(1) 摊销。如果字典很大而字符串不长这个转换的收益非常明显。另外注意内层循环遍历 j 的时候从 0 开始往前找。你可以先直观理解成从开头重新拼一句话看看拼到 i 的时候能不能拼出来但实际含义是枚举最后一刀的切点。再写记忆化搜索的版本。这个版本自顶向下思考更贴合人类直觉而且代码写起来也别有风味适合你在理解DP后作为巩固练习。def wordBreak(s: str, wordDict: List[str]) - bool: word_set set(wordDict) n len(s) memo [-1] * (n 1) def dfs(i): if i n: return True if memo[i] ! -1: return memo[i] for j in range(i 1, n 1): if s[i:j] in word_set and dfs(j): memo[i] 1 return True memo[i] 0 return False return dfs(0)记忆化搜索的思路是从下标 i 出发枚举当前要匹配的单词终点 j如果 s[i:j] 在字典里且从 j 出发的子串也能拆分那从 i 出发就能拆分。memo 数组记录每个位置的结果-1 表示没算过0 表示 false1 表示 true。注意这里我故意没用 True/False 作为 memo 的初始占位值因为如果 memo 里存布尔值初始值没法区分没算过和算过是false。用 -1 占位就不会有这个问题。对比一下两种方式的适用场景记忆化搜索适合先想清楚从一个位置往后怎么递归的问题代码更接近人的直觉自底向上DP则避免了递归调用栈的开销在极端情况比如字符串特别长、递归深度大下表现更稳。面试的时候我个人的建议是先写出一个能跑的方案然后主动跟面试官讨论另一种写法这比闷头写代码加分得多。5. 复杂度分析和边界条件细节决定成败先看时间复杂度。自底向上DP是两层循环外层 i 从 1 到 n内层 j 从 0 到 i-1所以总共 n*(n1)/2 次计算也就是 O(n^2)。每次循环里还有一个 substring 操作和 set 查找substring 的时间是 O(最长单词长度)但在代码里 s[j:i] 需要拷贝子串严格来说是 O(i-j)所以整体是 O(n^3) 最坏情况但如果把 j 的枚举顺序优化一下从 i-1 往前遍历只检查长度不超过字典最长单词的 j可以优化到 O(n * L)其中 L 是字典最长单词长度。很多进阶玩家会注意到这个优化先求 wordDict 中最长单词的长度 max_len然后内层循环的 j 只需要从 i-max_len 到 i-1因为 j 再小的话s[j:i] 的长度超过了字典中任何单词的长度必然不在字典里。这个优化在字典单词普遍很短的时候提升巨大代码改动也很小。空间复杂度方面dp 数组是 O(n)word_set 是 O(k)整体 O(nk)。记忆化搜索的 memo 数组也是 O(n)但递归调用栈在极端情况下会占额外的 O(n) 空间所以自底向上DP在空间上略优。边界条件有几个值得单独说第一dp[0] True 不能省。空串虽然不在字典里但它是拆分的基础。如果没有这个初始值dp[1] 就没有办法通过 dp[0] 推导出来。第二字典里的单词可能比 s 本身还长。比如 s abcwordDict [abcdef]这时相乘循环里 substring 的长度超过 n 的情况不该发生因为 substring 的区间本来就是 [j, i)其中 i 最大为 n长度不会超过 n。但如果你在记忆化搜索里枚举 j 的时候不小心用 range(i, n2)就会越界记得检查边界。第三题目说 s 非空但字典中的单词也是非空字符串。所以不用担心空串匹配的问题但你的代码里 dp[0] 仍然必须设为 true。第四s 中有字典之外的字符时比如 s applepenapplewordDict [apple, pen]程序会怎么处理前面apple匹配成功dp[5]true接着pen匹配dp[8]true最后又是appledp[13]true。如果某个字符根本不在字典里比如 s abcx字典只有 abc那么 dp[4] 计算时j3 时 dp[3] 可能为 falsej2、j1、j0 时 substring 分别是 cx、bcx、abcx都不在字典里dp[4] 保持 false。这个流程自己推一遍会很有帮助。6. 常见错误与高频调试实录这题在提交过程中有几个非常经典的坑我把它们整理成一个速查表每一行都是真实出现过的问题。常见错误具体表现根本原因解决方案字典没转set提交超时每次 substring 查找都是线性扫描整个字典开头加 word_set set(wordDict)dp数组越界内层 j 从 1 开始而不是 0忘了 dp[0] 是边界条件确认 j 从 0 取到 i-1substring拼写错误Java写 substringPython写 sub_stringAPI不熟代码review时逐行检查忘记break性能略差但不至于错找到合法切分后仍继续循环加 break 提前退出记忆化搜索memo初始值用False某些合法结果被误判为falseFalse和未计算冲突用-1/None做初始占位只考虑切一整个词结果永远false把dp[i]误当成s[0:i]本身在字典里逐字确认dp[i]的定义我在本地跑测试的时候还遇到过一个很隐蔽的问题Python 的 substring 切片是左闭右开s[0:4] 取的是下标 0、1、2、3 这4个字符。如果你写代码的时候脑子里想着前i个字符然后写 s[0:i]看起来没问题但如果写成 s[0:i1]就会多取一个字符结果整个dp全是错的。这类问题肉眼往往看半天也发现不了最好的办法是在小规模用例上把dp数组打印出来一步一步核。另一个调试技巧是写一个暴力回溯版本作为benchmark随机生成短字符串和简单字典两边结果对比一旦出现不一致就说明DP版本有bug。这种对拍式测试特别适合动态规划这类逻辑简单但容易写岔的题。还有一次我在LeetCode评论区看到有人问为什么自己的DP会超时贴出来的代码里字典没用set而是直接 list 查找。当时那个人的wordDict长度超过1000每次substring都要做1000次字符串比较不超时才怪。这就是一个典型的性能优化点。7. 从一道题看一类题字符串DP的套路总结刷完139题你应该有意识地去提炼字符串动态规划这类题的通用解法。这类题的标志性特征是给你一个字符串让你判断它能不能被某种规则切分、匹配、覆盖比如单词拆分、回文分割、正则匹配、编辑距离。它们的共同套路是什么核心是一种前缀递推的思想用 dp[i] 表示字符串的前 i 个字符满足某种性质然后通过枚举切分点 j或者与前缀的关系来构造转移方程。这类题以后你还会在 LeetCode 上碰到不少变体比如 140单词拆分II要求列出所有拆分方案、132回文分割II、91解码方法等。139题只是其中最简单的判断能不能拆。140题就在这个基础上加了一步不仅要判断能否拆分还要把所有拆分方案输出。那时你就会发现139题的DP只是热身真正的难点在于如何用回溯和记忆化来生成方案而dp数组里存bool还是存List的问题也会浮出水面。现在先把139的DP吃透到了140会轻松很多。我还想强调一点不要只背代码要把为什么 dp[i] 的定义是前 i 个字符想清楚。这个定义直接决定了循环的边界、切分的写法、以及后面变种题的迁移难度。面试的时候很多人背了代码但解释不清 dp[i] 的含义这种基础不牢在追问环节会露馅。8. 性能优化进阶从O(n^3)到接近O(n*L)前面提过枚举 j 的时候可以只从 i-max_len 到 i-1。这个优化的原理非常简单如果 s[j:i] 的长度大于 max_len那这个子串不可能等于字典里任何一个单词因为最长单词才 max_len 长。所以 j 只需要遍历 i-max_len 到 i-1 这个窗口。这样写的好处是内层循环的次数从平均 n/2 次缩减到最多 max_len 次。如果字典的单词都比较短比如都是3到5个字母max_len 很小整体时间复杂度可以认为是 O(n * max_len)也就是接近线性的。这个优化在竞赛或面试中属于加分项虽然不改变最坏情况但在实际测试用例上效果显著。还有一个更极端的优化是用单词表构建前缀树Trie然后在DP过程中沿着Trie边走边匹配子串这样可以把子串匹配的复杂度再降一步。但这个思路对139来说属于杀鸡用牛刀适合你去琢磨140题或者训练数据结构功底的时候尝试正常刷题我建议你先把 max_len 的优化写对就足够了。另外聊一下缓存字符串匹配结果的方法。如果你在一个很长的测试用例上反复调用 s[j:i] in word_set每次都要算哈希其实可以做个预处理把字典里所有单词按长度分组比如 group[len] {单词1, 单词2, ...}然后枚举 j 的时候只看 group[i-j] 这个长度对应的集合。但这个优化和 max_len 窗口优化作用有重复实际收益不大至少139的场景不用这么折腾。9. 面试现场怎么答这题才能加分如果你是在面试中遇到这道题这几点是你可以在解题之外主动展示的思辨能力。第一先确认字典大小和字符串长度的约束主动向面试官询问数据范围。这听上去像套话但它直接决定了你要不要做 max_len 窗口优化、要不要考虑前缀树。面试官喜欢看到你在大规模数据面前有意识地优化。第二解释 dp[0] True 的语义时不要说因为空串就是true更好的说法是它表示一个合法的起始状态没有它转移方程的第一步就没法走。这个解释虽然细节但能体现你对动态规划本质的理解。第三当面试官追问能不能用BFS做时要有一定准备。BFS的思路是把字符串的下标看成节点如果 s[i:j] 在字典里那么从 i 可以走到 j。这样问题就变成从 0 出发能不能到达 n也就是图上的可达性问题。BFS的时间复杂度也是 O(n * L)并且空间上比DP更省不需要dp数组只需要一个visited数组。这个思路在有些情况下甚至比DP更直观谈出来会很加分。第四如果面试官要求你写记忆化搜索你在写之前可以先把递归状态画出来f(i) 表示从位置 i 到末尾能否拆分。然后再写代码。我记得第一次刷这题的时候就是因为没想清楚 f(i) 的确切范围递归写出来总差一个单位。先在纸上画两行例子能少走很多弯路。10. 变种题的自然延伸走出139的舒适区这道题做完值得顺手做几个变种巩固一下知识迁移能力。第一个是LeetCode 140单词拆分II题目要求输出所有拆分方案。这题的解法是在139的判断基础上加回溯dp数组既可以用来判断可行性也可以在递归时用来剪枝——如果 dp[j] 是 false那就不需要继续递归。这里你会深刻地体会到可行性DP和方案枚举如何结合起来工作。第二个变种是LeetCode 472连接词。题目给一个单词列表找出其中可以由两个或以上其他单词拼接而成的单词。这题本质上是多次调用单词拆分但有个大优化把单词按长度排序从短到长处理并且用已经处理完的短词作为字典去验证当前单词是否可拆分。它会让你真正理解字典是动态变化的DP的状态空间和字典内容是深度耦合的。第三个变种是139的双向检查比如LeetCode 139 的一种变态版本s 两端都可以作为切分的起始点。这种题目在竞赛中出现得少但用来加深对无后效性的理解是很好的。我的建议是每一次刷题都要主动问自己这题换个问法我还会不会。139换到140从判断变成枚举难度瞬间上一个台阶再把题面改改从字典里的词拆分变成字典里的词拼接又是一个新题目。这种举一反三的练习比题海战术有效得多。