企业官网建设流程全解析

刷力扣动态规划专题的时候，有一道题我反复看了好几遍才真正吃透，就是力扣100题单里的第86题——单词拆分，对应原题是LeetCode 139。这道题的题面非常朴素：给定一个字符串s和一个单词列表wordDict，判断s能不能被拆分成若干个字典中出现的单词。看起来“回溯也能做”，但真正动手提交时才发现，朴素的递归回溯会在某些用例上直接超时。这篇文章就把我在这个题上踩过的坑、理清的思路、最后写出来的解法，以及还能延伸去哪里，完整地整理一遍，给正在按题单刷动态规划的朋友做参考。

先说结论：这道题是典型的线性动态规划，核心是定义“前 i 个字符是否可拆”这个布尔状态，再用子串是否在字典中来转移。它表面是个字符串题，本质上是个“判定前缀是否可达”的模型。理解了它，后面做单词拆分II、完全背包类题目都会顺很多。

1. 题目拆解：先搞清楚“单词拆分”到底在问什么

1.1 题意与若干容易被忽略的细节

题目会给一个非空字符串s和一个包含若干单词的列表wordDict。要求判断s是否可以由字典中的单词拼接而成。这里有几个细节，刷题时很容易踩：

• 字典里的单词可以重复使用，也就是说同一个单词可以出现在最终拆分结果的任意多个位置，不受次数限制。
• 拆分时不允许有剩余字符，s的所有字符必须全部被覆盖。
• 分隔符本身不参与匹配，我们只是在逻辑上把s切成若干段，每段都必须能命中字典。
• 字典中可能存在重复单词，但去不去重一般不影响判断结果。最稳妥的办法是转成哈希集合。

举个例子，s = "leetcode"，wordDict = ["leet", "code"]，答案是 true，因为可以拆成"leet" + "code"。再比如s = "applepenapple"，wordDict = ["apple", "pen"]，答案是 true，因为可以拆成"apple" + "pen" + "apple"，注意这就是“单词可重复使用”的体现。但s = "catsandog"，wordDict = ["cats", "dog", "sand", "and", "cat"]，答案是 false，因为无论怎么组合，都没办法把整个字符串无遗漏地覆盖掉。

第一遍做的时候，很多人会下意识地觉得这就是个“字符串匹配 + 递归”的问题：从开头开始，尝试用字典里的每个单词去匹配前缀，匹配成功就递归处理剩余部分。这个想法本身没有错，但性能是完全不够的。

1.2 为什么暴力回溯一定超时

假设我们写一个递归函数dfs(start)，它表示从s[start]开始能否拆完。每次递归都遍历字典中的所有单词，尝试匹配前缀，匹配成功就继续递归dfs(start + len(word))。这个思路在字典很小、字符串很短的时候能跑出结果，但一旦数据规模上来，复杂度立刻失控。

最典型的反例就是s = "aaaaaaaaaaaaaaaaaaaaaaa"，wordDict = ["a", "aa", "aaa", ...]。从第一个位置开始，每次都有多个单词可以匹配，于是递归树会呈现出指数级的分支增长。理论上最坏情况下，这个递归树的规模会随着字符串长度指数爆炸。即使加了“如果已经匹配就提前返回”之类的剪枝，本质上仍然是在尝试所有拆分方案，而不是利用已经计算过的结果。

我在本地测试过一个长度为 30 的纯a字符串、字典包含"a"到"aaaa"时，朴素回溯跑了十几秒都没结束。这时候就应该意识到，需要把子问题的结果缓存下来，或者直接改成自底向上的数组递推。这也就是动态规划切入的时机：问题可以被切分成互相重叠的子问题，并且当前状态只依赖更小的状态，天然适合用 DP。

从另一个角度看，“单词拆分”本质上是一个字符串前缀的覆盖问题。字符串长度是固定的，我们只需要知道每个前缀“能不能拆”，而不关心它具体是怎么拆的。这种“只问能不能、不问怎么拆”的判断题，几乎都是动态规划的主场。

2. 动态规划思路：从“能不能拆”到“前缀可拆”

2.1 状态定义是怎么想出来的

动态规划入门时最痛苦的就是“状态到底怎么定”。这道题的状态其实可以这样推导：对于字符串s，如果我们已经知道它的某个前缀s[0..j)可以被字典中的单词完整覆盖，那么只需要再检查从j到i的这一段s[j..i)是否在字典中出现，就能推导出s[0..i)也可以被覆盖。

换句话说，设dp[i]表示s的前i个字符（即s[0..i)）能否被字典中的单词拼接出来。这里的“前 i 个字符”是一个左闭右开区间，写代码时对应s.substr(0, i)。之所以定义成前i个字符而不是以i结尾的子串，是因为我们需要一个自然的起点：前 0 个字符，也就是空串，它应该被视作可以覆盖的状态，这样所有长度为 1 的合法前缀才能从它身上转移过来。

很多教程会直接给出dp[i]的定义，然后让你背下来。但如果你自己想一遍整个过程，就会发现这个定义几乎是“顺理成章”的：枚举当前前缀的结束位置i，再枚举它的最后一段是从j开始的，这样整个问题就被拆成“前面j个字符可不可拆”和“s[j..i)在不在字典里”两个独立的子问题。前者是已经被算出来的dp[j]，后者查一下哈希表就行。

2.2 状态转移方程的推导细节

状态转移方程可以写成：

dp[i] = true 当且仅当 存在 j ∈ [0, i)，使得 dp[j] == true 且 s[j..i) 在 wordDict 中

从实现的角度来看，我们需要两层循环：外层枚举i，也就是当前要判断的前缀长度，从 1 到n；内层枚举j，也就是上一段已经覆盖到的位置，从 0 到i-1。只要找到一个j满足条件，就可以把dp[i]置为 true，并且提前跳出内层循环。

这里最容易产生疑问的是内层循环的方向。有人会写成j从i-1倒着往 0 枚举，也有人会从 0 正着枚举。两种方式在正确性上都可以，因为dp[i]依赖的所有dp[j]都满足j < i，而我们在外层循环中已经把dp[0..i-1]全部算完了，所以倒序枚举不会产生“用了还没算出来的状态”的问题。

不过从“剪枝效率”来看，如果先知道字典中最长单词的长度maxLen，那么当j < i - maxLen时，s[j..i)的长度已经超过maxLen，它不可能出现在字典中，这些j完全没必要枚举。于是内层循环可以写成从max(0, i - maxLen)开始。这个优化在字符串特别长、字典单词长度差异很大的时候，能明显减少子串截取和哈希查找的次数。

还有一点要注意：dp[i]只表示“存在至少一种拆分方案”，并不记录具体方案。这是这道题的关键简化。如果需要输出具体拆分结果，那就是 LeetCode 140 单词拆分II 要做的事，后面我会专门聊。

2.3 初始化和边界条件

初始化时，dp[0]必须为 true。原因前面已经说了：空串不需要任何单词就能拼出来，它是所有后续状态转移的基石。如果dp[0] = false，那么所有长度大于 0 的状态都无法从空串转移过来，结果会全部变成 false，这显然不对。

边界上还有一个容易忽略的点：如果wordDict是空的，那除了dp[0]以外，其他所有的dp[i]都应该保持 false，因为没有任何单词可以用来覆盖字符串。代码里自然就能处理这种情况，不需要单独加 if。

另外，如果s本身就在字典中，那么dp[n]会在j = 0时被置为 true。这里没有特殊处理，完全靠转移方程自然完成。如果你在代码里发现整串单词命中的用例输出错误，检查一下是不是把dict.count(s.substr(0, i))写成了dict.count(s.substr(1, i))，这种下标错误是新手最容易犯的。

2.4 时间复杂度与空间复杂度分析

用哈希集合存储字典，每次判断子串是否在字典中平均是 O(1) 的时间。两层循环枚举了所有i和j的组合，数量大约是n * (n+1) / 2，也就是 O(n^2)。每次内层还需要截取子串s[j..i)，截取操作本身是 O(i-j) 的，所以严格来说总复杂度是 O(n^3)，其中n是字符串长度。

但实际提交时，大部分测试用例都能通过，因为字典中的单词一般不会太长，而且我们通常会在内层循环里尽早 break，真正截取的子串数量远小于理论上限。如果做了maxLen剪枝，内层枚举次数会被限制在maxLen附近，实际时间接近 O(n * maxLen)，非常快。

空间复杂度是 O(n)，用来存dp数组。如果考虑哈希集合存储字典，空间复杂度还要加上字典单词的总字符数 O(totalLen)，但这部分通常不参与面试时的复杂度讨论，因为它是输入本身就占用的空间。

3. 代码实现与实操细节

3.1 最容易写错的C++实现

我先把这道题最标准的 C++ 解法贴出来，然后逐行讲几个容易写错的地方。

class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> dict(wordDict.begin(), wordDict.end()); int n = s.size(); vector<bool> dp(n + 1, false); dp[0] = true; for (int i = 1; i <= n; ++i) { for (int j = 0; j < i; ++j) { if (dp[j] && dict.count(s.substr(j, i - j))) { dp[i] = true; break; } } } return dp[n]; } };

第一处容易写错的是dp数组的大小。我见过有人写成vector<bool> dp(n, false)，然后循环从 0 到 n-1，结果边界判断一团糟。这里建议统一用n + 1，下标从 0 到n，dp[i]对应前i个字符，这样语义清晰，也不容易出现“差一错误”。

第二处是s.substr(j, i - j)的写法。注意substr的第二个参数是“长度”，不是“结束位置”。substr(j, i-j)表示从下标j开始，取i-j个字符，正好是s[j..i)这个左闭右开区间。这个写法我在第一次写的时候差一点就写成了s.substr(j, i)，那就是把第二个参数理解成了结束位置，截出来的字符串会完全不对。

第三处是break的位置。一旦找到某个j使dp[i]为 true，就不需要再枚举更小的j了，因为我们的目标只是“判断是否可拆”，而不是“统计拆法数量”。忘了break不会导致答案错误，但会白白消耗时间，在一些极端用例上会拖慢速度。

3.2 Python版本的实现与一个小优化

Python 写起来更短，但有一个细节值得注意：对 Python 来说，s[j:i]这种切片操作也会创建新字符串。虽然写起来很自然，但在内层循环里反复切片仍有一定开销。加上一个基于maxLen的剪枝会让代码在实际运行中快不少。

class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: word_set = set(wordDict) max_len = max(len(w) for w in wordDict) if wordDict else 0 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 word_set: dp[i] = True break return dp[n]

这个写法把内层循环的起始点从 0 改成了max(0, i - max_len)，逻辑依据是：如果s[j:i]的长度大于max_len，那它必然不在字典里，检查它纯属浪费。枚举的j越少，切片次数越少，整体耗时下降非常明显。实测在s特别长、字典单词又短的情况下，这个优化能把运行时间缩短好几倍。

max_len的初始化还有一个坑：如果wordDict为空，直接max(len(w) for w in wordDict)会抛异常。所以我在前面加了一个if wordDict else 0的保护。虽然题目通常默认字典非空，但作为习惯，这类防御性写法还是值得保留的。

3.3 Go实现版本

Go 的字符串切片不会生成新字符串，它是基于原字符串的一个视图，所以s[j:i]的开销比其他语言小很多。这也是 Go 在字符串动态规划题上比较舒服的一个原因。

func wordBreak(s string, wordDict []string) bool { wordSet := make(map[string]bool) for _, w := range wordDict { wordSet[w] = true } n := len(s) dp := make([]bool, n+1) dp[0] = true for i := 1; i <= n; i++ { for j := 0; j < i; j++ { if dp[j] && wordSet[s[j:i]] { dp[i] = true break } } } return dp[n] }

这版没有加maxLen剪枝，因为它已经能通过所有测试用例了。面试时用 Go 写的话，建议先写这个最直白的版本，讲清楚思路，再提一句“可以通过最长单词长度做剪枝”来体现优化意识。

3.4 面试官视角：这几行代码里藏着的考点

刷题不能只满足于“能通过”，面试时这道题往往还会引出几个追问。第一个追问是：为什么dp[0]要是 true？这个问题本质上是在考察你对边界条件合法性的理解，而不是背答案。第二个追问是：内层循环能不能倒着写？能，因为所有依赖的状态都已经算完了，但要能解释清楚为什么安全。第三个追问是：如果我用记忆化递归实现，复杂度一样吗？一样，dfs(i)表示前 i 个字符是否可拆，每次递归枚举字典单词尝试匹配，加缓存后每个状态只计算一次。区别在于记忆化搜索是“用到才算”，迭代 DP 是“全部算完”，两者在本题性能上几乎没有差别。

如果面试官再往下深挖，可能会问“为什么不是贪心”。这是这道题最经典的一个坑：单词拆分不能用“最长前缀匹配”或者“优先匹配短单词”之类的贪心策略来解。比如s = "aaaaaaa"，wordDict = ["aaaa", "aaa"]，如果贪心地优先匹配更长的"aaaa"，会剩下"aaa"，刚好能匹配，看起来没问题；但构造一个反例并不难：s = "abcde"，wordDict = ["ab", "abc", "de"]，如果贪心匹配"abc"，剩下的"de"能匹配，没问题；可如果字典里有"abcd"，贪心匹配"abcd"后剩"e"就无法匹配了，而正确的拆分是"ab" + "cde"（假设"cde"在字典里）。这类构造让我彻底明白了为什么必须枚举所有切分点，而不能只盯着某一个位置的匹配结果。

4. 变体与延伸：一道题串起一类动态规划

4.1 单词拆分II：不仅要判真，还要输出方案

LeetCode 140 是这道题的姊妹篇，要求输出所有可能的拆分结果。这时候dp[i]只存 bool 就不够用了，一般有两种做法：一种是让dp[i]存一个布尔值，先用它判断整个字符串是否可拆，再做带回溯的 DFS 收集所有方案；另一种是让dp[i]直接存所有能组成前 i 个字符的最后一个单词的集合，再用递归拼接。

这里最值得借鉴的经验是：一定要先做“可行性判断”再回溯。如果字符串根本不可能被拆分，直接回溯会在大量无效路径中空转，而一趟dp判断只需要 O(n^2) 的时间，划算得多。我在写 140 的时候，第一次就是直接上 DFS，遇到一个长字符串的不可拆用例直接卡到怀疑人生，后来加了前置 DP 判断，立马就过了。

这个“先判可行性、再搜方案”的思路，其实在很多问题里都通用。你不需要一开始就求所有方案，而是先确认“有没有解”，因为无解时搜索会遍历整个状态空间；有解时通常解的数量也有限，搜索起来反而没那么可怕。

4.2 与完全背包问题和爬楼梯的对照

很多人在刷完这道题后会隐约觉得它有点像背包，但又说不上来哪里像。我来拆一下：完全背包问题是说有一组物品，每个物品可以无限取，问能否装满容量为 target 的背包，状态转移通常写成dp[j] = dp[j] || dp[j - w[i]]。单词拆分无非是把“背包容量”换成了“字符串前缀长度”，把“物品重量”换成了“单词长度”，把“能否放入”换成了“这一段子串是否是字典中的单词”。

至于爬楼梯，dp[i] = dp[i-1] + dp[i-2]是只有固定步长的情况，而单词拆分相当于“步长不固定，且跨出的每一步必须对应一个合法单词”。这样一对比，你就能看出动态规划模型之间的共通性：都是通过枚举最后一步/最后一个物品来分解问题。面试时被问到“你还做过哪些类似的题”，完全可以用这个视角把爬楼梯、完全背包、单词拆分串起来讲。

反过来看，如果字典里所有单词长度都一样，比如都是 2，那这道题就退化成了一个类似“每次跳固定长度”的问题，状态转移只剩一个固定位置可枚举，复杂度也随之降低。理解了这个退化过程，你对 DP 状态设计的理解会更深一层。

4.3 实际场景：分词、协议解析和敏感词过滤

不要觉得动态规划只活在面试题里。单词拆分这个模型在真实工程里也有不少对应物。最直观的是“分词”：如果我们有一个已知的词典，要把一段用户输入切分成连续的词条序列，比如输入法里的拼音转汉字、搜索引擎里的查询词切分，背后都有类似的“前缀匹配 + DP 找最优切分”思想。当然工业界的分词通常还要考虑词频和最大概率，而不是单纯判断“可不可拆”，但核心状态机一模一样。

另一个场景是协议解析。某些二进制协议中，消息体是由已知类型的数据块拼接而成的，我们需要判断一个缓冲区是否由合法的数据块序列组成。把每个类型的数据块看成字典里的单词，缓冲区的字节流看成字符串，这个问题就变成了一个“字节级”的单词拆分。我在做嵌入式相关开发的时候，就碰到过用类似 DP 的思路去校验一段拼接报文的合法性。

还有敏感词过滤。如果敏感词库可以看成字典，用户输入的文本需要判断是否包含任意敏感词组合，那这更像是“字符串中是否存在字典子串”的问题，通常会转成 AC 自动机来做。但如果你要做的是“整段是否完全由白名单词组成”，那单词拆分的 DP 就是一个合理的暴力方案。这类迁移能力，才是刷题刷到最后真正有价值的地方。

5. 常见问题与调试实战

5.1 状态转移方向写反会怎样

我见过的最典型的错误，是把转移方程误写成“如果s[j..i)在字典中且dp[i]可拆，则dp[j]也可拆”，也就是把状态从前向后推。这在感觉上像是在拼积木：先拼好后面的，再推前面。但dp数组是从小到大计算的，dp[i]还没算完，又用它去推dp[j]，其中j > i，结果就是不断用到未初始化的值，最终答案基本全是 false。

调试这种问题有个快捷办法：在循环里打印dp数组的变化过程。如果发现某个dp[i]被置 true 后又莫名变回 false，那大概率是有人覆盖了它，或者循环边界不干净。正常情况下dp[i]一旦为 true 就不该再变了。

另外，如果把s.substr(j, i-j)写成s.substr(i, j-i)，那截取出来的字符串完全是反的，也会导致答案错误。这类下标问题用一个小用例s = "abc", wordDict = ["a", "bc"]就能定位：如果输出 false，说明转移方程或者截取方式有问题，需要重点排查。

5.2 用记忆化搜索等价实现的思路

有些朋友对自底向上的dp数组不太敏感，但对递归比较熟。这题的递归写法也很简单：

from functools import lru_cache class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: word_set = set(wordDict) @lru_cache(None) def dfs(i): if i == len(s): return True for j in range(i + 1, len(s) + 1): if s[i:j] in word_set and dfs(j): return True return False return dfs(0)

注意这里dfs(i)表示“从下标 i 开始的后缀能否拆完”，跟迭代版里“前 i 个字符”是镜像关系。lru_cache(None)相当于手动维护了一个 memo 字典。实际运行中，如果字典单词很多，这个递归写法会在每个位置都尝试所有可能的单词，虽然缓存避免了重复计算，但函数调用开销会比迭代版大一些。想稳一点的话，可以在递归里也加maxLen剪枝：只枚举j到min(len(s), i + max_len)。

面试时如果你觉得迭代版解释起来费劲，先写记忆化搜索，再说“这个思路其实等价于自底向上的 DP，我可以顺手改成数组版本”，会是很自然的演进式表达。

5.3 值得保存到本地的一组自测用例

我整理了一些我在刷题时用来自测的用例，覆盖了各种容易出现边界问题的场景。

最后一个空串用例很有意思，LeetCode 的s默认非空，但不少本地测试模板会把空串带进来。如果dp[0] = true，空串的答案自然为 true；如果你把初始条件写错成dp[0] = false，这个用例就会暴露问题。

5.4 一个关于字符集大小的优化方向

如果题目明确说字符串只包含小写字母，那么还有一种优化思路：把字典中的单词都转成某种哈希值，或者用 Trie 来加速前缀匹配。用 Trie 的话，在内层循环里可以一边沿着字符走一边收集所有可能匹配到的单词长度，这样就不需要为每个j都做一次整段子串的哈希查找。

思路是这样的：构建一棵包含所有字典单词的 Trie。当我们固定了i，想让dp[i]为 true 时，可以反过来枚举从某个j开始匹配，也可以直接从i往前回溯尝试。但更自然的做法是，在计算dp[i]时，从s[i]开始往 Trie 里逐步插入字符，只要某个节点是单词结尾，并且dp[i - len]为 true，就可以把dp[i]置为 true。这样每个位置只需要遍历到 Trie 的深度为止，实际复杂度接近 O(n * maxLen)，而且省去了大量字符串哈希的计算。不过这种写法在面试中属于加分项，不是必须的。先把基础 DP 写对，再提 Trie 优化，更容易给面试官留下好印象。

我个人做完这道题之后，很长一段时间里遇到“判断字符串是否能由某些片段拼接”的问题，都会下意识地想“能不能用 dp[i] 表示前缀可不可达”。这个思维习惯确实帮我节省了很多思考时间。比如后来做“拼接最大长度”、“单词接龙”之类的题目，都能很快套上同一个框架。如果你正处在动态规划的入门阶段，建议把这道题从“看懂题解”练到“闭着眼睛能写出来”，再去碰 LeetCode 140 和一道完全背包的题。等这三道题都吃透了，你会发现动态规划不再是玄学，而是一种可以复制粘贴的思维模型。