1. 项目概述动规入门绕不过去的“分词题”LeetCode 139题“单词拆分”是我刷动态规划时遇到的一道经典题目。题目本身不复杂给定一个非空字符串s和一个包含若干单词的字典wordDict判断s能否被拆分成一个或多个字典中出现的单词且拆分时可以重复使用字典中的单词。乍一看很多人第一反应是“这不就是字符串匹配吗”于是直接上find()或者正则结果发现测试用例一多就各种翻车。我当年第一次做这题时也没少踩坑后来系统地整理了一遍才真正理解这道题的妙处。它表面上是字符串处理实际上是动态规划入门阶段最典型的状态转移题之一与“爬楼梯”“最大子序和”一样都是用一维DP就能解决但难点在于状态定义和转移方程的建立方式。这道题适合三类人刚接触动态规划不久的初学者可以用来巩固“子问题拆解”思维准备面试的开发者这是多家互联网公司常考的原题或变体对字符串算法感兴趣的人通过这题能了解“字典匹配 状态缓存”这类通用套路。之所以用一整篇文章来写这道题是因为我后来发现把这题吃透之后再去做“分割回文串”“单词拆分II”以及一些需要分段处理的算法题思路会顺畅很多。可以说LeetCode 139是理解“分段型DP”的第一块敲门砖。2. 整体设计与思路拆解为什么暴力解法会超时2.1 初看题目时的三种直觉解法先说说大多数人看到这道题的第一反应。我试过三套方案各有各的问题。第一套是“暴力遍历字典”直接用字典里的每个单词去s里做匹配匹配到就从头截掉然后重复这个过程。直觉上很像“拼积木”以为只要不停地从原字符串头部切掉能匹配上的单词最后剩下空串就说明能拆分。但这个方法一个反例就能打回去s applepenapple字典[apple, pen]从头部切会先匹配到apple剩下penapple再切pen剩apple这时如果字典里没apple就误判为不可拆分。如果调整顺序先切applepen如果它在字典里结果又不同。也就是说从头部贪心地切并不保证全局最优必须考虑所有拆法。第二套是“正则表达式”^(apple|pen)$。这种方案在白名单比较小、单词数量少的时候能用但字典一长正则引擎内部会构造一个巨大的状态机空间和时间开销都不可控而且wordDict可能是动态传入的去拼正则本身就是一种隐性的性能坑。第三套是“递归枚举所有拆分位置”。这个思路方向是对的——把字符串拆成所有可能的“前缀 剩余部分”前缀在字典里就继续递归处理剩余部分。但如果不加缓存递归树会指数级膨胀。比如一个长度为n的字符串有n1个拆分点最坏情况下所有前缀都在字典里计算量接近 2^n。LeetCode的测试用例里专门准备了这种极端情况直接超时没商量。2.2 为什么这题本质上是“分段决策问题”把递归枚举的过程画出来会发现一件很重要的事递归树上大量节点是重复计算的。比如处理leetcode时如果先切出leet剩下code需要判断如果先切出l、e、e、t再拼起来最终还是会走到“判断code能否拆分”这一步。也就是说问题的状态可以用“字符串的一个后缀”来唯一描述。判断“原字符串从某个位置i开始的后缀能否拆分”这个问题不依赖前面是怎么拆分的只依赖这个后缀本身的内容和字典。这时候就用得上动态规划了。动态规划的核心思想就是把原问题拆成若干子问题记录子问题的答案避免重复计算。放在这题里就是用一个布尔数组dp[i]表示“原字符串的前i个字符能否被成功拆分”。有了这个定义转移方程就变成dp[i] dp[j] wordDict.contains(s.substring(j, i))其中0 j i如果能找到任何一个j使得前j个字符可以拆分且s[j:i]从j到i这个区间正好是字典里的一个单词那么前i个字符就可以拆分。这个方程的直观含义是站在字符串的某个位置i往回看前面有一段子串正好命中字典同时之前的[0, j)区间已经确认是可拆分的那[0, i)就万事大吉了。2.3 为什么用一维数组而不是二维数组很多初学者会下意识地想用dp[i][j]表示从i到j的子串是否可拆然后再合并区间。这种区间DP思路有它的适用场景——比如处理回文子串时二维数组是标准解法——但在这题里大材小用了而且让状态转移变得非常复杂。关键在于单词拆分问题具有“前缀可复用”的性质一旦前j个字符的拆分结果确定了这个结果对后面所有位置都是固定不变的。它不需要像回文串那样同时关心中间段的对称性只需要前置状态就够了。用一个一维布尔数组就能完整记录所有需要的历史信息这也是动态规划“状态压缩”的一个基础案例。3. 核心细节解析与实操要点状态定义和转移写法3.1 状态定义的关键dp[i]到底代表什么写这道题之前必须先完成一件看似不起眼但极其重要的事情把dp数组的下标含义钉死不然后面写代码一定会混。我用的是dp[i] true表示s的前i个字符即s[0..i-1]这个子串能否拆分成字典中的单词。注意这里有个细节dp[0]代表空字符串。空字符串当然可以“拆分”成零个单词所以dp[0] true。这个初始值看似是一句废话实际上是整个转移方程的基石。没有dp[0] true遇到s的第一个字符就能匹配上完整单词的情况时dp[i]就无从转移。dp[s.length()]是最终答案表示整个字符串的拆分结果。这里我踩过一个坑有段时间我把dp[i]理解为“前 i 个字符已经处理完剩余的是s[i:]”然后去判断后缀能不能拆。这种做法也能做对但需要倒着遍历代码写起来不够直观。从前向后推进更符合人的思维习惯也方便排查边界问题。所以还是推荐dp[i]表示前缀可拆。3.2 双重循环遍历时的两种姿势明确了状态定义下一步就是写转移方程的实现。常见写法有两种外层循环遍历“终点位置”内层循环遍历“起点位置”或“单词”。先说最标准的前缀型写法def wordBreak(s: str, wordDict: List[str]) - bool: word_set set(wordDict) # 把字典转成集合查找复杂度降到O(1) n len(s) dp [False] * (n 1) dp[0] True # i表示当前要判断的前缀长度 for i in range(1, n 1): # j表示拆分点把s[0:i]分成s[0: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[n]这个双层循环的时间复杂度是O(n^2)严格说还需要乘上子串截取和哈希查找的代价但通常按O(n^2 * m)或O(n^2)理解空间复杂度O(n)。对于 LeetCode 的测试规模来说完全够用。另一种写法是“枚举起点再枚举字典里的单词”本质上没变但思路略有不同for i in range(n): if not dp[i]: continue for word in wordDict: end i len(word) if end n and s[i:end] word: dp[end] True这种写法的好处是它是“从已知可行前缀向外扩展”只要前i个字符可拆分就尝试把字典里的每个单词拼接到后面能拼上就更新对应的终点状态。这种转移角度更适合理解“状态推进”的思维方式而且天然地利用了字典信息省去了一些无效的子串判断。两种写法最终效果一样我个人的经验是第一种符合“决策型DP”的思考方式写起来不容易漏第二种在需要“从可用工具集合里挑选”的场景下更自然。建议两种都写一遍对理解转移的本质很有帮助。3.3 一个小优化预计算最大单词长度如果wordDict很长比如几千个单词而s相对较短内层循环仍然会对每个j都做子串截取和哈希判断。这时候可以提前算一下字典中所有单词的最大长度max_len把内层循环的范围限制在j i - max_len的范围里max_len max(len(w) for w in wordDict) for i in range(1, n 1): for j in range(max(0, i - max_len), i): if dp[j] and s[j:i] in word_set: dp[i] True break这个优化的原理很简单如果s[j:i]的长度超过了字典里所有单词的最大长度那s[j:i]必然不在字典里这种拆分点直接跳过即可。当字典很大而目标字符串长度一般时这个优化能剪掉大量无效分支实测是有效果的。4. 实操过程与核心环节实现从暴力递归到记忆化再到 DP4.1 从递归开始暴露重复计算问题我建议学习这道题时先写一个纯递归版本哪怕它超时也要写一遍。因为很多人在学动态规划时会陷入“记模板”的误区跳过直觉构建直接套递推式结果题目一变就不会了。先看递归版本def wordBreak(s: str, wordDict: List[str]) - bool: word_set set(wordDict) n len(s) def dfs(start: int) - bool: if start n: return True for end in range(start 1, n 1): if s[start:end] in word_set and dfs(end): return True return False return dfs(0)这段代码逻辑完全正确但在s很长且字典包含很多单字母单词的情况下会超时因为dfs(1)、dfs(2)这些状态会被反复计算。如果你在本地跑一个小例子加上一个计数器会看到调用次数指数增长。边写边想dfs(start)的入参是当前要处理的后缀的起始位置。返回值是这个后缀能不能被拆分。start n时说明字符串已经处理完返回真否则枚举end作为拆分点只要前缀在字典里且剩余部分能拆分就返回真。这个递归天然对应了“分段决策”的直觉。4.2 加上 memo把递归变成“自顶向下动态规划”递归之所以慢是因为同一状态被算了多次。解法在“剪枝”之上其实还有更简单的一层加缓存。def wordBreak(s: str, wordDict: List[str]) - bool: word_set set(wordDict) n len(s) memo {} # 用字典记录已计算的start结果 def dfs(start: int) - bool: if start n: return True if start in memo: return memo[start] for end in range(start 1, n 1): if s[start:end] in word_set and dfs(end): memo[start] True return True memo[start] False return False return dfs(0)“记忆化搜索”的本质是“先递归再查表”对比“先填表再递推”的DP两者只是实现顺序不同底层是对同一个状态图在搜索。加缓存之后每个位置只会被计算一次时间复杂度立即降到O(n^2 * m)级别。这一步是理解“自顶向下”和“自底向上”这两种DP风格的关键。4.3 为什么最终推荐自底向上的表格式DP既然记忆化搜索已经解决了超时问题为什么面试和竞赛标准答案通常给表格DP一个很现实的原因是表格DP没有递归调用栈的开销更稳递归在某些语言里深度过大可能触发栈溢出Python默认递归深度约1000层测试用例里一个长字符串可能直接崩另外表格DP的代码可预测性更强调试时打印dp数组就能直观地观察整个状态的推导轨迹。我打一个生活化的比喻记忆化搜索像是“出门前先查手机地图”走到一个路口再决定下一步表格DP像是“提前规划好整条路线”按顺序一步步执行即可。前者灵活但依赖“实时计算”后者一次成型、性能更稳定。刷题时这两种方法我都建议掌握但面试时优先写表格DP因为它不容易被递归深度刁难。4.4 完整可运行的 Go 版本示例下面给出一个 Go 版本用于演示另一种语言环境下同样的DP写法func wordBreak(s string, wordDict []string) bool { wordSet : make(map[string]bool, len(wordDict)) maxLen : 0 for _, w : range wordDict { wordSet[w] true if len(w) maxLen { maxLen len(w) } } dp : make([]bool, len(s)1) dp[0] true for i : 1; i len(s); i { start : i - maxLen if start 0 { start 0 } for j : start; j i; j { if dp[j] wordSet[s[j:i]] { dp[i] true break } } } return dp[len(s)] }在业务场景中这类“给定一个字典判断长串能否由字典词拼接”的代码常见于关键词过滤、文本分段、命令解析等模块整体思路是相通的。5. 常见问题与排查技巧实录5.1 字典包含重复单词时会不会出问题不会。用set(wordDict)去重之后重复单词完全不影响判断结果。但如果你写的是“遍历字典里的每个单词并逐个匹配”的版本重复词只会白白增加几轮无效循环。这里有一个小建议在算法开头把wordDict转成set不仅是为了去重更是为了把in判定的时间复杂度从O(k)降到O(1)。5.2 拆分时是否允许使用同一个单词多次题目允许而且在我们的dp转移中天然支持。比如s aa字典[a]dp[1]和dp[2]都能正确变成true因为每次只判断“当前子串是否在字典里”并不消耗字典中的词条配额。如果题目改成“每个单词最多用一次”那状态就必须额外记录字典的使用情况复杂度要大很多但LeetCode原题没有这层限制。5.3 测试用例里的字符串很长直接用 Python 的切片会不会慢确实会慢。Python 的s[j:i]每次都会生成一个新字符串如果n很大切片本身的开销不可忽略。有一种优化是先计算所有单词的长度或哈希值再逐个比对但 LeetCode 的测试集用常规解法就能过。我在实际开发中如果遇到超高吞吐文本解析会改用“后缀数组”或“AC自动机”这类更重的工具但这就是另一篇博文的内容了。5.4 一个隐蔽的边界问题dp[0] 必须为 true这个坑我在第一次写时踩过。如果不设dp[0] true第一个能匹配完整前缀的单词就无法完成状态转移。比如s abc字典[abc]遍历到i 3、j 0时dp[0]为falsedp[3]也永远是false。建议写代码前先在注释里标出dp[0]的特殊含义能省不少调试时间。5.5 如何验证自己的 DP 推导是否正确我常用的一个方法是“跟着代码手跑一个短用例”。比如s leetcode字典[leet, code]初始化dp[0] truei 4时j 0dp[0]为真且s[0:4] leet在字典里所以dp[4] truei 8时j 4dp[4]为真且s[4:8] code在字典里所以dp[8] true返回dp[8]结果为true如果结果不符合预期就把dp数组打印出来一目了然。5.6 面试追问能否输出一种具体拆分方案这题最常见的变体是 LeetCode 140单词拆分II要返回具体拆出来的单词列表。思路是把dp数组从“布尔值”升级成“存储可行前驱位置列表”。比如dp[i]存放所有满足dp[j]true且s[j:i]在字典里的j值最后从n倒着回溯就能构造完整的路径。需要注意的是结果数量可能是指数级的如果需要全部返回只靠一个dp可能还不够还要配合回溯法或记忆化搜索来做结果合并。6. 变体与扩展这道题还能怎么用6.1 从“判断能否拆分”到“统计拆法数量”LeetCode 139更进阶的变体是不只要知道能不能拆还要知道有多少种不同的拆法。这时候只要把dp[i]从布尔值改成整数dp[0] 1 for i in range(1, n 1): dp[i] 0 for j in range(i): if dp[j] and s[j:i] in word_set: dp[i] dp[j]这其实是很多计数类DP的标准套路就像“凑硬币”里的计数版本一样。一旦理解了“布尔DP能升级成计数DP”你会发现自己对动态规划的理解会有一层新的飞跃。6.2 从“字典是集合”到“字典是前缀树”当字典规模巨大时每次都从j开始逐个试i的效率会下降。常见优化是把wordDict构建成一个 Trie前缀树然后从当前的j开始走 Trie如果中途匹配到一个完整单词就尝试转移。这个方法在wordDict很大、单词平均长度短的时候效果显著能把内层循环从遍历所有可能子串转化为只遍历能匹配到的路径。当然为了刷题过这题不推荐一上来就上 Trie。先用朴素的set dp写对再在理解的基础上做优化练习路径会更平缓。6.3 在真实业务里能做什么我从2020年前后就一直在做自然语言处理相关的东西用到的字符串分段处理和这种 DP 很像。真实场景比如长文本中的敏感词词典匹配判断、词法分析器的 token 切分验证、简写还原甚至某些搜索引擎的“查询词拆分”都能借鉴这种“前缀状态字典判断”的思想。不过要注意真实业务里往往还有上下文依赖、优先级、歧义消解等约束LeetCode 139 的模型是极度简化的它能解决“纯字典匹配”这层问题但不能照搬到完整的中文分词系统里。理解它的边界才是一个工程师的正确姿势。7. 最后的实操提示这题的三个“锚点”写到这里再做一个小的收束。这道题做了几遍之后我给自己总结了三句话每句对应一个代码重点做题时默念一下就能避开九成问题dp[0] true空串必须视为可拆分这是转移的起点遍历i时内层j枚举的是拆分点dp[j]与s[j:i]同时满足时dp[i]才能置真一旦找到一个可行拆分点立刻break后面不用再看了。最后再补充一个不常被人提到的经验如果你在面试时实在写不出 DP用记忆化搜索也能答出“可行解”只不过要主动说明这就相当于自顶向下的DP并能在面试官的引导下完成复杂的表格化改造这一点往往能挽回不少印象分。从实际刷题角度看这题我前后做过四遍每次隔一段时间再写都能发现新的理解层次。强烈建议你也隔一两周回刷一次重点观察“自己是否还会犯dp[0]漏设、break忘写、set忘转换”这三类低级错误。能稳定避免这些说明入门DP的关键节点已经通过了。
