LeetCode 139 单词拆分全解析：动态规划、剪枝优化与 Trie 加速

刷 LeetCode 的人几乎都会被一道叫“单词拆分”的题拦住过。它排在热门 100 题的中段题干看起来非常简单给一个字符串和一个字典问这个字符串能不能被字典里的单词完整拼出来。但第一次动手写的时候很容易在贪心、回溯和动态规划之间绕圈子。LeetCode 139 单词拆分Word Break要解决的事情说到底就是一句话给定非空字符串s和存放单词的字典wordDict判断s是否可以拆分成一个或多个字典中出现的单词单词可以重复使用拆分时不能打乱顺序也不能留下间隙。这道题看起来像是“字符串匹配”实际考的是动态规划里的状态设计也是面试中出镜率很高的一道经典题目。它适合正在学动态规划、又不想只停留在理论推导的同学当入门练手题也适合准备面试的人用来训练“从题干到状态定义”的思维路径。接下来我会把这题的几种主流解法、背后的原理、常见优化手段、面试追问角度以及我自己刷题时踩过的坑全部拆开讲一遍。1. 题目到底在考什么从题干到动态规划的直觉1.1 先看懂题意别急着写代码题目给你一个字符串s比如leetcode再给你一个单词列表比如[leet, code]。让你判断s能不能拆成字典中的单词。这里要特别注意三点字典里的单词可以重复使用不要求每个单词只出现一次。拆分后的单词必须严格按照原字符串顺序拼接回来不能重排。整个字符串要被完整覆盖既不能丢掉字符也不能有多余的字符。我个人喜欢把这题比喻成“乐高积木”。字典里的每个单词是一块固定形状的积木s是一段已经搭好的长条模型你需要判断能不能用手里这些积木块一块挨着一块地把模型完整铺满积木块可以反复用但必须严丝合缝。很多第一次刷这题的人容易误解成“看看s里能不能找到字典里的单词”于是直接用了暴力搜索或者贪婪匹配。实际题目要求的是“整体是否能被覆盖”这个区别非常关键。就像catsandog这个例子字典是[cats, dog, sand, and, cat]虽然cat、cats、sand、and、dog都能在字符串里找到但它们无法拼出完整的catsandog所以答案是 false。这也是为什么简单地在字符串里搜索一遍是不够的。1.2 贪心为什么错得离谱遇到这种“能不能拼出来”的问题第一反应很可能是贪心从前往后扫遇到字典里匹配的单词就切掉然后继续处理剩下的部分。这个思路听起来很顺实际跑起来却经常翻车。我常用一个很简单的反例字符串是abcd字典是[abc, ab, cd]。从前往后贪心匹配先看到abc能匹配切掉剩下一个d字典里没有整体判断为 false。但实际上abcd完全可以拆成abcd答案是 true。问题就出在你在abc这个位置选了匹配反而把后面唯一的正确路径ab cd给堵死了。这就说明了一个本质问题单词拆分是一个多阶段决策问题当前局部选哪个单词匹配会影响后面所有阶段的选择。贪心只考虑“当前能匹配”不考虑“匹配之后还能不能走到最后”所以在这个题上注定失效。顺着这个思路往下想你会发现我们需要一种能记录“到达每个位置是否可行”的机制这样后面的阶段就不用重新从零决策而是要依赖前面阶段的结果。这就是动态规划的切入点。1.3 动态规划的状态与转移怎么来的既然贪心不行那就把问题拆成子问题。把字符串s分成两段前j个字符和后i - j个字符。如果前j个字符能被字典拆开而且从j到i的那段子串本身就是一个字典里的单词那么前i个字符也就能被拆开。用这个思路状态定义就出来了dp[i]表示字符串s的前i个字符即s[0:i]能否被拆分成字典中的单词。边界条件是dp[0] true因为空前缀可以被看作已经拆分完成。转移方程可以写成dp[i] true当存在 j i满足 dp[j] true 且 s[j:i] 在字典中拿s leetcode、wordDict [leet, code]来走一遍dp[0] true当i 4j 0时dp[0]为 true且s[0:4] leet在字典中所以dp[4] true当i 8j 4时dp[4]为 true且s[4:8] code在字典中所以dp[8] true最终返回dp[8]为什么这个状态是合理的因为它把“原问题是否能拆分”转化成了“前缀是否可拆分”而前缀的子问题规模更小天然满足动态规划的最优子结构。再加上同一个前缀可能被多条路径走到如果不记录结果就会反复计算这也叫重叠子问题。这两条性质正是用动态规划解题的必要条件。2. 三种主流通用解法与横向对比2.1 自顶向下记忆化搜索先从最容易理解的递归搜索写起。核心思路是定义一个递归函数dfs(start)表示从下标start开始到字符串末尾的部分能否被成功拆分。递归出口是start n也就是已经到达末尾说明整条路径拼通了。但直接写成纯 DFS 会超时原因很好理解同一个start会被很多路径反复访问。比如字符串一长、字典里的单词组合很多dfs(2)可能被dfs(0)经过好几种不同单词组合触发每次都重新递归一整棵树复杂度直接指数爆炸。解决办法是加缓存用lru_cache把每个start的计算结果存下来。代码如下from functools import lru_cache def wordBreak(s: str, wordDict: List[str]) - bool: words set(wordDict) n len(s) lru_cache(None) def dfs(start: int) - bool: if start n: return True for end in range(start 1, n 1): if s[start:end] in words and dfs(end): return True return False return dfs(0)这段代码的执行逻辑是从start开始尝试所有可能的结束位置end只要某一段子串在字典里并且剩余部分也能拆开就返回 true。加了缓存以后每个start最多被计算一次每种状态对应的枚举仍然要遍历end所以整体复杂度接近O(n^2)的量级。记忆化搜索对我来说还有一个额外的好处它天然贴合人的思考方式先想“这个位置能不能拆出去”再递归判断后面。面试时如果紧张不容易写出索引错误。2.2 自底向上递推动态规划的经典写法还是递推。从dp[0] true出发依次计算dp[1]、dp[2]一直到dp[n]。对于每个i遍历所有可能的j看是否存在一个分割点让dp[j]为 true 且子串s[j:i]在字典里。def wordBreak(s: str, wordDict: List[str]) - bool: words set(wordDict) n len(s) # dp[i] 表示 s 的前 i 个字符能否被成功拆分 dp [False] * (n 1) dp[0] True for i in range(1, n 1): for j in range(i): # 前 j 个字符可拆分且子串 s[j:i] 是一个字典单词 if dp[j] and s[j:i] in words: dp[i] True break return dp[n]这个写法有两点需要特别提醒。第一dp数组长度是n 1不是n因为要存空前缀这个状态。第二内层循环只要找到一个可行的j就可以break了不需要继续枚举因为dp[i]是布尔值找到一个证据就够。递推写法的好处是容易用表格模拟。你在草稿纸上画出长度为n 1的一行格子从左往右填每个格子的值取决于它左边某些格子是否为 true以及对应子串是否命中字典。一旦你习惯了这种填表视角动态规划题就很难再觉得抽象了。2.3 队列 BFS把位置当成图节点同一个问题换个视角还能用 BFS 来做。把下标位置看成图的节点下标0是起点下标n是终点。如果s[start:end]是一个字典单词就认为存在一条从start到end的边。那么问题就变成了是否存在一条从0到n的路径。from collections import deque def wordBreak(s: str, wordDict: List[str]) - bool: words set(wordDict) n len(s) q deque([0]) visited [False] * n while q: start q.popleft() if start n: return True if visited[start]: continue visited[start] True for end in range(start 1, n 1): if s[start:end] in words: q.append(end) return False这里visited数组用来防止同一个位置被重复入队。为什么不直接用dp标记而要多写一个visited因为 BFS 里一个位置一旦从队列弹出并确认不可行理论上不用再处理但同一位置可能被多个不同来源的边入队不判重会导致队列膨胀。BFS 的复杂度也在O(n^2)量级而且它和记忆化搜索在本质上共享同一个图模型区别只在于遍历顺序。面试时提一嘴 BFS 解法能让面试官觉得你对同一个问题有多个建模视角这是加分项。2.4 三种解法怎么选解法核心思路时间复杂度空间复杂度适用场景记忆化搜索递归 缓存重叠子问题约 O(n^2)O(n)逻辑直观适合手写草稿动态规划递推从左到右填布尔表约 O(n^2)O(n)最推荐代码最简洁BFS位置建图判路径可达约 O(n^2)O(n)适合迁移到图思维题我个人在面试里会先讲动态规划递推因为代码最短也最容易让面试官听懂状态定义。然后主动补充记忆化搜索和 BFS 的视角展示自己知道同一种状态可以用不同方式遍历。最后强调如果面试官要求优化再引出下面要讲的剪枝和 Trie 方案。3. 剪枝优化与工程化细节3.1 利用字典最长单词长度缩小枚举范围回到递推代码内层循环每次都从j 0枚举到j i - 1。但实际上很多j是完全不可能命中的如果s[j:i]的长度超过了字典里最长单词的长度那这一段子串无论怎么切都不可能在字典里存在。于是可以提前算好max_len max(len(w) for w in wordDict)只枚举长度不超过max_len的j区间。def wordBreak(s: str, wordDict: List[str]) - bool: words set(wordDict) max_len max(len(w) for w in words) n len(s) dp [False] * (n 1) dp[0] True 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 words: dp[i] True break return dp[n]这一步的优化效果在字典单词长度差异大时特别明显。比如字典里最长单词只有 10 个字符那么每个i最多只需要检查 10 个j内层循环规模从O(n)降到了O(max_len)整个算法复杂度变成O(n * max_len)对超长字符串非常友好。我一直建议写代码时顺手把这个max_len算上因为它的成本只有一行max收益却是一个数量级的循环缩减。3.2 字符集快速过滤还有一种极端场景字符串s很长字典也很大但s里包含了一个字典里所有单词都不含有的特殊字符。这种情况下无论怎么拆都无法成功直接返回 false 就行。具体做法是统计字典中所有单词出现过的字符集合chars_in_dict再检查s中每个字符是否都在这个集合里。只要有一个字符不在直接判定不可拆分。chars_in_words set() for w in wordDict: chars_in_words.update(w) if any(c not in chars_in_words for c in s): return False这个优化本身很简单但它能在很多“看上去能拆、实际上有一个致命字符”的用例上节省大量时间。我遇到过类似aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab这种字符串字典里全是a、aa、aaa之类的词因为最后一个字符是b字典里没有任何单词含b这时候字符集过滤直接就能返回 false根本不用进入动态规划循环。3.3 语言层面的实现提醒很多人在 Python 和 Java 里写着写着就忽视了切片操作的代价。Python 的s[j:i]和 Java 的s.substring(j, i)都会创建新的字符串对象。当你频繁在循环里调用substring时即使算法思路正确常数因子也会偏大。有两类改进办法。一是配合max_len剪枝从源头减少切片次数二是把字典换成 Trie从当前字符开始沿着前缀树匹配而不是反复切出子串再查询哈希表。这两条路我在下一节和第五章都会详细展开。这里只想提醒一句刷题测试时不会暴露问题但到了真实大语料场景切片带来的 GC 压力是你不得不考虑的。4. 进阶玩法从 139 到输出所有拆分方案4.1 从“能不能拆”到“怎么拆”LeetCode 上还有一道姊妹题 140 单词拆分 II要求不仅判断能不能拆还要把所有合法拆分方案都输出。比如s catsanddog、wordDict [cat, cats, and, sand, dog]要求输出[cats and dog, cat sand dog]。139 的布尔 DP 只记录“是否可达”丢掉了路径信息。要输出所有方案一种自然的思路是先跑一遍 139 的可行性判断如果不可行直接返回空列表如果可行再用回溯或记忆化 DFS 生成所有路径。4.2 记忆化 DFS 直接返回方案列表把每个位置能拼出的所有句子缓存起来dfs(start)返回从start到末尾的所有合法拆分结果。递归时枚举end如果s[start:end]在字典中就把它和dfs(end)返回的每个句子拼接起来。def wordBreak(s: str, wordDict: List[str]) - List[str]: words set(wordDict) n len(s) memo {} def dfs(start: int) - List[str]: if start n: return [] if start in memo: return memo[start] res [] for end in range(start 1, n 1): word s[start:end] if word in words: for tail in dfs(end): res.append(word if not tail else word tail) memo[start] res return res return dfs(0)这里的拼接逻辑要注意当tail是空串时直接把word加入结果否则用空格连接。很多人在递归出口返回[]而不是[]是因为空串代表“已经拆完了”可以和前面的单词拼接出完整句子如果返回空列表上层的循环会直接把整条路径丢掉。4.3 回溯阶段的代价分析输出所有方案在极端情况下会指数爆炸因为方案数量本身就是指数级别的。比如s aaaaaa...字典是[a, aa]合法拆分方案极多。这无法从算法层面根本避免因为你必须输出每个方案。但有一件事可以做总体可行性预判。如果不先跑 139 的 DP 判断直接进入回溯遇到那些本来就不可拆分的字符串时会沿着错误分支一路递归到底部产生大量无效调用。以s很长且字典无法覆盖尾部为例纯回溯会在每个前缀处疯狂分支最终全部返回空浪费巨大。先做一次布尔 DP把不可行情况直接挡在门外回溯只处理真实可行的输入这是我在实际测试里感受到的最明显优化。5. 面试中被追问的优化方向5.1 状态还能压缩吗一维dp数组已经达到了O(n)的空间复杂度这基本就是这个模型的极限了。虽然dp[i]依赖前面很多位置看起来不能用标准的滚动数组优化但在实现层面可以换用比特集压缩。比如用BitSet代替布尔数组每个下标占 1 bit用位运算批量检查前一位是否为 true并直接把新到达的位置批量置位。这种做法在 C 和 Java 里都能写适合处理超长字符串但面试中除非面试官明确问“能不能更快”否则不必主动展开。更多的是考察你是否理解一维 DP 已经天然压掉了二维状态。5.2 字典很大时用 Trie 加速单词匹配如果单词数量特别多哈希集合的contains查询虽然是 O(1)但substring的生成成本和哈希计算的成本会累积。更好的办法是把字典建成前缀树Trie在扫描字符串时沿着树边推进走到任意一个单词结束节点就把对应位置标记为 true。class TrieNode: def __init__(self): self.children {} self.is_end False def wordBreak(s: str, wordDict: List[str]) - bool: root TrieNode() for w in wordDict: cur root for ch in w: cur cur.children.setdefault(ch, TrieNode()) cur.is_end True n len(s) dp [False] * (n 1) dp[0] True for i in range(n): if not dp[i]: continue cur root j i while j n and s[j] in cur.children: cur cur.children[s[j]] j 1 if cur.is_end: dp[j] True return dp[n]这段代码的关键在于它不是对每个i都枚举所有j而是只从dp[i] true的位置出发沿着字典树匹配所有可能的单词终点。匹配过程中一旦某个字符在字典树中不存在就立即停止不需要继续往后查。字典公共前缀越多这种方案的收益越明显。面试时如果提到 Trie建议同时说明“哈希集合适合词典量小、哈希计算快的情况Trie 适合公共前缀明显、字典规模大的场景”这样比只丢出一个方案要专业得多。5.3 相关联的经典题目有哪些单词拆分属于“字符串 动态规划 是否能拆分成合法子串”的一类题。比较经典的同类题包括LeetCode 131 分割回文串求所有分割方案核心是预处理回文表后回溯。LeetCode 72 编辑距离二维 DP在字符间做替换、插入、删除决策。LeetCode 10 正则表达式匹配带模式匹配的动态规划处理*和.的状态转移。LeetCode 140 单词拆分 II就是本章讲的输出所有方案版本。把这题刷明白之后再看这些题会轻松很多。它们共通的一个套路是先明确定义“从哪到哪的子串是合法的”再设计dp[i]表示前缀结果最后考虑是否要回溯输出路径。最近很多人刷题时会顺带聊周赛内容比如 073 爱吃香蕉的狒狒这类二分答案题、周赛 430 里的一些组合题其实都属于“识别问题类型”的训练。单词拆分教会你的是识别“拼接可达性”问题这比背模板重要得多。6. 刷题现场实验记录与避坑清单6.1 我跑过的几组关键测试用例自己刷题时我会用一个固定测试集合验证代码是否可靠输入 swordDict期望输出leetcode[leet, code]trueapplepenapple[apple, pen]truecatsandog[cats, dog, sand, and, cat]falseabcd[abc, ab, cd]truea[b]falseaaaaaaa[aaa, aaaa]true[]注意题目规定 s 非空但边界要心里有数这几个用例基本覆盖了字符串可拆、不可拆、贪心会误判、单个字符、单词长度重叠等常见情况。每次改优化方案时我都会把这组用例重新跑一遍确保剪枝没有改坏原有逻辑。6.2 四个让你与 AC 失之交臂的坑忘记把dp[0]设为 true。很多新手从dp[0] true这一步就开始漏导致所有依赖空前缀的判断全部失效。数组长度写成n而不是n 1。遍历s[0:i]时i能取到n所以数组必须多开一格。把左闭右开区间搞反。s[j:i]包含下标j不包含下标i。如果你写成s[j:i1]不仅越界还会把正确的拆分判断错。递归搜索不缓存。基础 DFS 写法在普通用例能通过一到长字符串就超时。这不是思路问题是实现缺少了重叠子问题处理。6.3 答题顺序与一点心得体会如果是在面试现场我建议按这个节奏来先用 30 秒说明题目本质是“前缀拼接可达性”问题再用一个例子演示dp[i]的含义接着写出递推代码最后补一个max_len剪枝。整个过程控制在 8 到 10 分钟既清晰又显示出你对复杂度有感知。我自己一开始做这题时也曾在贪心的思路上卡了很久总觉得“先匹配掉一个单词”怎么会有错。后来用abcd那个反例把自己说服之后才对“为什么需要记录所有前缀状态”有了切肤之感。这题真正教给你的不是记住一个 DP 模板而是理解“当前决策影响全局结果”的问题不能只顾眼前。等你把 139 和 140 都刷透之后再回头看其他字符串领域的动态规划题会发现很多卡点都迎刃而解。