LeetCode 139 这道“单词拆分”在力扣热题100的榜单上排在第86位是很多刷题党绕不过去的一道动态规划题。题目本身不长给你一个字符串 s 和一个字典 wordDict判断 s 能不能被拆分成若干个字典中出现的单词。第一眼看过去像字符串处理本质上却是完全背包类的动态规划典型代表你在面试里遇到的“给你一堆零件问能不能拼成目标”的题十有八九都能往这套 dp 思路上套。这篇文章不会直接丢一个标准答案给你而是把我从第一次用 DFS 暴力搜到完全吃透 dp 数组含义的过程完整走一遍顺带聊聊那些只有测试用例才逼得出来的边界坑。适合刚开始刷动态规划、或者热题100刷到一半卡住的朋友看完争取一遍写对。1. 题面拆解这道题到底在问什么1.1 题目真正描述的场景题目原文不长我用自己的话翻译一遍输入一个字符串 s以及一个字符串列表 wordDict问你可不可以通过在 s 中插入空格把它变成一句完全由字典中单词组成的句子并且字典中的单词可以重复使用。难点在于“重复使用”四个字第一次读题的人很容易忽略导致后续思路跑到组合问题上去。跑几个例子会立刻清晰示例1s leetcodewordDict [leet, code]结果是 true。因为可以在“l-e-e-t”和“c-o-d-e”之间切一刀。示例2s applepenapplewordDict [apple, pen]结果是 true。它可以切分成 apple pen apple同一个单词 apple 在第一段和第三段重复使用了。示例3s catsandogwordDict [cats, dog, sand, and, cat]结果是 false。你可能第一时间想到 cat sand og但 og 不是字典单词再试 cats and og依然卡在 og 上甚至 cat s and og 更不行。这个例子特别典型它提醒我们只要存在一种拆法把整个串切完就算成功但你必须照顾到所有可能的切分位置漏掉任何一个状态都可能误判。1.2 约束条件才是真正的复杂度风向标如果刷题只看示例不看约束很容易走弯路。原题给了三个关键约束s 的长度不超过 300wordDict 中最多 1000 个单词字典单词可能长短不一但不会包含空字符串。这个约束组合决定了什么我算给你看。s 长度为 300 时n² 就是 90000 次状态转移现代计算机处理起来毫无压力。要是 s 的长度变成 10^5n² 的算法就会非常吃力那时候可能要借助字典树加滚动优化完全就是另一个难度层级的题目了。所以对这道题而言O(n²) 是标准预期复杂度你不用在极端优化上纠结先把 dp 思路写对比什么都重要。1.3 为什么说它是“背包类动态规划”第一次接触“背包”概念的同学会懵背包不是把物品塞进有限容量吗这题哪来的容量其实你把 s 的总长度 n 当成背包容量把字典里的每个单词当成物品单词在字符串里匹配一段就是在“占用”一段长度单词可以反复取用所以它是标准的完全背包问题。这个视角不是硬拗的后面写代码时你会发现它的循环结构跟完全背包的模板高度相似。提前建立这个认知对梳理 dp 数组的含义会有很大帮助。2. 一上来就写 DFS 暴力回溯为什么一定会被教育2.1 最直觉的思路从索引 0 开始试着切大多数人的第一反应不是动态规划而是“切字符串”。我当时的写法长这样def wordBreak(s, wordDict): word_set set(wordDict) n len(s) def dfs(pos): if pos n: return True for end in range(pos 1, n 1): if s[pos:end] in word_set and dfs(end): return True return False return dfs(0)这段代码的用意很朴素从当前位置 pos 出发枚举下一个切分点 end如果 s[pos:end] 在字典里就递归判断剩余部分任何一条路径能走到字符串尾巴就说明可以拆分。小样例一跑立刻通过人很容易产生“已经写对了”的错觉。但这时候千万别急着提交先想想后面会发生什么。2.2 指数级最坏情况是怎么产生的暴力回溯最怕的组合是字典里的单词特别短字符串又特别长导致每个位置都有很多种切法。比如 s 是一长串 aa...a 加一个 b 结尾字典里有 a、aa、aaa 等一堆由 a 组成的短词。递归从开头开始每一步既能切 1 个字符也能切 2 个、3 个分支数量会随字符串长度快速膨胀最后形成指数级的搜索树。LeetCode 的测试用例里有专门针对这种裸 DFS 的超时数据很多同学的第一次 TLE 就是这么来的。即使没有碰上恶意数据中间状态的重复计算也够让人头疼。比如从 pos 5 和 pos 7 都可能递归到 pos 9而 pos 9 往后无解那么两条路径都会把 pos 9 的失败搜索重新完整执行一遍。可 pos 9 的结果是固定的算一次就够了。这种重复累积起来暴力递归的耗时会被放大得很厉害。2.3 记忆化救一把复杂度如何瞬间降下来给 dfs 加个缓存其实很简单记录“从 pos 出发能否拼完”。一旦某个位置的结果算出来之后再碰到就直接返回不用重新展开搜索。def wordBreak(s, wordDict): word_set set(wordDict) n len(s) memo [-1] * (n 1) def dfs(pos): if pos n: return True if memo[pos] ! -1: return memo[pos] 1 for end in range(pos 1, n 1): if s[pos:end] in word_set and dfs(end): memo[pos] 1 return True memo[pos] 0 return False return dfs(0)加完缓存后每个 pos 最多被真正计算一次每次计算要枚举 end 从 pos 到 n所以复杂度从指数级直接降到 O(n²)。如果你是面试现场能在此基础上想到记忆化已经能说明你有动态规划的直觉了。但作为系统刷题我更推荐接下去的自底向上 dp 写法理由会在第 4 章说明。3. dp 状态怎么设计把“能不能拆”翻译成数组3.1 为什么前缀长度是天然的状态划分维度动态规划最难的地方从来不是写转移方程而是把状态定义想清楚。对这道题来说最自然的观察对象是字符串的“前缀”。字符串的前缀具有严格的递推关系长前缀的合法性可以由短前缀加上一个字典单词推导出来。定义 dp[i] 表示 s 的前 i 个字符也就是 s[0:i]能否被拆分为若干个字典单词。这里要特别注意i 指的是长度而不是下标。比如 s leetcodedp[4] 对应的是 leet 能否拆分而不是 s[4] 这个字符本身。这样定义的好处是字符串切片 s[0:i] 的左闭右开区间天然对应我们想要验证的内容后续写代码时不会出现下标差一的混乱。有一个认知坑必须说透dp[0] 表示空字符串空串当然可以被拆成“零个单词”所以 dp[0] True。这不是数学上的强行规定而是为了让递推跑通的起点。很多第一次写的人把 dp[0] 设为 false于是 dp[0] 无法给任何长前缀提供基础整张 dp 表全盘皆输。3.2 状态转移方程和一条完整的手推过程假设 dp[1] 到 dp[i-1] 都已经算好现在要算 dp[i]。最朴素的思想看前 i 个字符能不能由某个已经合法的短前缀再接上一个字典单词构成。也就是说要找一个切分点 j满足两个条件dp[j] 为 true前 j 个字符能拆完s[j:i] 正好等于字典中的某个单词。两个条件同时成立就可以在 j 的位置切一刀左边已经拼好右边是一个完整单词于是 dp[i] 为 true。只要存在任何一个满足条件的 jdp[i] 就定为 true。写成转移方程就是dp[i] OR( dp[j] s[j:i] in wordDict )其中 0 ≤ j i拿示例手动推一遍会更直观。s leetcodewordDict [leet, code]dp[0] True。i 1j 只能取 0s[0:1] l 不在字典dp[1] False。i 2、3 同理全是 False。i 4j 0 时dp[0] True 且 s[0:4] leet 在字典中于是 dp[4] True。i 8 时j 4 时dp[4] True 且 s[4:8] code 在字典中于是 dp[8] True。最终返回 dp[8]也就是 dp[n]代表整个字符串可被拆分。整个过程看起来像切香肠每次只验证当前前缀的最后一个单词其他部分交给更短的 dp 状态。3.3 遍历顺序为什么必须是“先 i 后 j”dp 的循环顺序不能乱。外层 i 从 1 到 n表示我们逐个确认越来越长的前缀内层 j 从 0 到 i-1 遍历可能的切分点。这样安排的依据是dp[i] 依赖的是更短的 dp[j]j 必然小于 i。只要按照前缀长度从小到大计算算 dp[i] 时所有 dp[j] 已经全部就绪这就是自底向上递推的前提。如果外层先枚举 j再枚举 i你就可能在 dp[i] 还没算出来的时候就拿它的值去推导别的状态这会让递推关系彻底乱掉。从背包视角再看一遍完全背包的一般写法是外层遍历容量内层遍历物品。这里外层 i 就是容量前缀长度内层 j 遍历的是“上一个切分点”相当于在检查上一件物品放在哪个位置。两套思路在这里完全对上了这也是为什么很多经验丰富的刷题人一眼就能看出这道题的背包本质。4. 完整实现与复杂度备忘从标准写法到剪枝优化4.1 教科书版 Python 实现最标准的写法长这样class Solution: def wordBreak(self, 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千万别用原来的 list 做 in 判断list 的 in 是线性查找set 是哈希查找字典单词上千时差距会非常明显。第二内层一旦确认 dp[i] 为 true马上 break我们只关心能不能拆分不关心有多少种拆分方式找到一种就够了。第三最后返回的是 dp[n]不是 dp[n-1]很多人栽在这里。4.2 Java 版本与语言细节如果面试要求手写 Java我会给出下面这个版本class Solution { public boolean wordBreak(String s, ListString wordDict) { SetString set new HashSet(wordDict); boolean[] dp new boolean[s.length() 1]; dp[0] true; for (int i 1; i s.length(); i) { for (int j 0; j i; j) { if (dp[j] set.contains(s.substring(j, i))) { dp[i] true; break; } } } return dp[s.length()]; } }需要注意的是 Java 的 substring(j, i) 是左闭右开取的是 s[j] 到 s[i-1]正好对应长度为 i-j 的子串。这一点和 Python 的 s[j:i] 语义完全一致写起来反而很省心。另外Set.contains 每次都是 O(1) 复杂度的哈希查找这是 Java 版本高性能的关键别写成 list.contains。4.3 max_len 剪枝用最长的单词限制搜索范围上面的标准写法已经是 O(n²)。但有一个简单且安全的优化字典里最长的单词长度是 max_len那么一段能匹配的子串长度不可能超过 max_len。内层循环里如果 i - j max_len这个 j 就不可能形成合法匹配可以直接跳过。既然要跳过那些过长的子串不如把内层循环改成倒序遍历让子串长度从小到大递增一旦找到答案就能立刻 break。class Solution: def wordBreak(self, 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): for j in range(i - 1, max(i - max_len - 1, -1), -1): if dp[j] and s[j:i] in word_set: dp[i] True break return dp[n]这次内层循环从 i-1 往下走到 i - max_len 为止。倒序的意义在于j 越接近 i子串 s[j:i] 越短先用短词尝试命中一旦命中整个 dp[i] 就定案不用再管更长的切分方式。复杂度也从 O(n²) 变成 O(n × max_len)当 max_len 远小于 n 时收益尤其明显。LeetCode 的常见测试里 max_len 通常在 10 到 30 之间这么剪一下实际运行时间能快出不少。4.4 初始化 dp[0] 之后的一段思维校验代码写完别急着跑先对着几个特殊用例做“思维编译”。第一个用例是 s awordDict [b]。遍历 i 1j 0发现 s[0:1] a 不在字典中dp[1] 为 false返回 false结果正确。第二个用例是 s wordDict [a]。虽然原题大概率不会给空字符串但为了严谨即使 s 为空dp[0] true直接返回 true语义上空串可以由零个单词组成也说得通。第三个用例是 s aaaawordDict [a]。max_len 1所以每次内层只检查 j i-1dp[i] 都能从前一个状态推过来最终返回 true。这三个用例覆盖了“完全不可拆”“空串”“单个短单词反复使用”三类边界是提交前最有效的自查手段。4.5 复杂度纵向对比表实现方式时间复杂度空间复杂度适用场景裸 DFS 回溯最坏指数级O(n) 递归栈只适合理解题意记忆化 DFSO(n²)O(n)面试时的过渡方案标准自底向上 DPO(n²)O(n)通用、推荐首选DP max_len 剪枝O(n × max_len)O(n)字典单词较短时更高效看到这张表你可能会问既然记忆化 DFS 也是 O(n²)为什么我更推荐自底向上原因很实际递归函数在 LeetCode 上偶尔会暴露 Python 递归调用开销的问题而且自底向上的 dp 是后续做空间压缩、改写成背包问题的基础。面试官追问一句“能不能优化”从自底向上 dp 出发也更好接话。复杂度这件事满足题目约束就是合格优先保证代码可靠。5. 这些边界条件提交时真的会把你坑哭5.1 dp[0] 的初始化理解比记忆重要几乎所有人第一次写都会在 dp[0] 上犯嘀咕。有人觉得空字符串不能拆成单词就把 dp[0] 设为 false结果整个 dp 数组永远算不出 true。记住dp[0] true 不是对空串的“语义承认”而是递推的起点。它的意义是“从头到第 0 个字符这段不需要消耗任何单词就能拼完”。这样当 s[0:i] 本身就是一个字典单词时dp[i] 才能通过 dp[0] 被推导成 true。你越是试图从现实语义去解释空串越容易把自己绕进去把它当成一座桥就好。5.2 字典里有重复单词或互为前缀的单词题目没有禁止 wordDict 里有重复单词用 set(wordDict) 或 new HashSet(wordDict) 去重后重复项自然消失。比重复更隐蔽的是互为前缀的单词比如 leet 和 leetcodecat 和 cats。这类数据不影响 dp 正确性因为状态转移只看“当前子串是否在字典里”不会因为匹配了更长的单词就否定短单词的存在。切分是逐步完成的即便中途选择了短单词后续仍然可以拼接出整句。这是 dp 拆分的灵活性所在不用担心“贪心选长词一定更优”这种常见误解。5.3 剪枝和等价变形别弄丢状态含义有一种听起来很合理的“优化”内层循环从 i-1 倒着跑碰见 dp[j] 为 true 就尝试子串匹配。这本身没问题但有人会顺手把条件里的 dp[j] 改写成一个由切片长度推导出来的式子比如 dp[i - len(s[j:i])]。假如倒序遍历i - len(s[j:i]) 恰好等于 j看起来成立一旦改成正序遍历这个式子很容易因为索引变成负数而越界或者引入莫名奇妙的错误。这里的教训是优化别改状态含义。老老实实用 dp[j] 判断左边合法性用 s[j:i] in word_set 判断右边完整性左右境界清晰可读性也高。5.4 Python 切片的隐性开销和索引问题Python 的 s[j:i] 在 j i 时会返回空字符串这种“不报错”的特性经常掩盖笔误。写内层循环时最好保证 j i别依赖切片的默认行为。另一个细节是Python 切片本身会创建新字符串虽然 n 最大 300 时无所谓但在系统设计面试里如果说“字符串长度可达 10^6”你就得开始考虑避免频繁切片可以改成基于 startswith 或者逐字符比较的写法。一个更工程化的做法是维护每个单词长度只在长度匹配时才去比较字符串从源头减少无谓的字符串生成。5.5 提交后 TLE 时怎么快速定位如果提交超时不要盲目加优化。先看你的解法是不是漏了缓存这是最常见的 TLE 来源再看是不是没有对 wordDict 做 set 去重最后才考虑 max_len 剪枝。定位方式也很粗暴本地跑一个 s 长度 200 左右、字典全是短单词的极端数据肉眼观察耗时。如果明显卡顿多半是内层循环里做了太多次切片或 list 查找。把这三件事逐项排查大多数 TLE 都能当场解决。6. 做完这道题之后真正可以举一反三的方向6.1 从“能不能拆”到“怎么拆”单词拆分 IILeetCode 上有配套的进阶题要求不仅返回 true / false而是把所有拆分出的合法句子都列出来。做法是在 dp 确认可行之后从后往前回溯找到所有切分位置。dp 表在这里的一大价值就是剪枝如果 dp[j] 为 false那从 j 之前的状态就没必要继续回溯可以整段跳过。没有这层剪枝你会重复搜索大量无解前缀数据稍长就直接爆掉。这相当于把“可行性判断”和“方案生成”两件事分层处理思路非常清晰。6.2 完全背包视角下的一串变体题一旦你建立了“背包容量 可重复取物品”的视角很多题都能串联起来。比如组合总和问题给定一串数字和 target问能不能用数字反复相加凑出 target套到单词拆分里就是把字符串替换成数字序列把单词替换成每个数的“单位贡献”。再比如零钱兑换问凑出目标金额最少需要几枚硬币它和单词拆分共享同一套外层遍历容量、内层遍历物品的骨架只是 dp 值从 boolean 变成了最值。真正有价值的不是多刷几道题而是能识别出这些题背后的公共结构。6.3 长字符串场景和字典树优化方向如果面试官加码说 s 的长度可能到 10^6你该怎么答这时 O(n × max_len) 的哈希查找虽然已比重心集合查找好但仍可以在每个位置用字典树对候选单词做前缀匹配把“从当前位置出发能匹配哪些单词”变成一次树上的多分支查找。也就是说外层移动 i 时维护一条字典树上的匹配路径每当某个节点表示单词结束就顺手更新对应位置的 dp。这种写法复杂度接近 O(n × max_len) 甚至更低但代码复杂度明显上来了。作为热身先把 max_len 剪枝版本吃透就够了字典树知道原理、能讲清适用条件已经比大多数候选人完善。6.4 面试实战中的讲解顺序如果你在面试现场遇到这道题我个人建议的讲述顺序是先给裸回溯和它的问题再自然过渡到记忆化接着从记忆化提炼出 dp 的状态定义最后给出自底向上的标准写法。这个过程看起来“绕路”但它向面试官完整展示了你把指数级暴力转化为多项式级 DP 的思维链路而不是背答案。每次讲到状态转移都停顿一下解释 dp[j] 为 true 且子串在字典中两个条件缺一不可这是整场面试的加分点。如果面试官性格直接你也可以先把标准 dp 写出来再补充一句“为什么可以加 max_len 剪枝”同样能体现对复杂度细节的掌控。个人经验是单词拆分这道题值得做三遍第一遍练手感用记忆化 DFS 想通递归结构第二遍用自底向上 dp 把转移方程落实第三遍再回头做单词拆分 II把回溯生成方案的道路彻底走一遍。三遍下来你不仅拿下了热题100这一道连带着把字符串 dp 和完全背包的关联也一并理顺了。下次再碰到类似题目第一时间想到的就不再是“背模板”而是“原来这还是那套 dp”。