企业官网建设流程全解析

前几天在群里看到有人问LeetCode 139这道单词拆分，说自己花了大半小时写了套递归，样例全过，一提交就超时。这问题我太有共鸣了——当年我刷LeetCode 139单词拆分的时候，同样在“怎么把递归改成动态规划”这一步卡了两天。今天这篇不想只贴一份标准答案糊弄人，我想把这道题从暴力递归到动态规划再到BFS的完整推导过程、边界条件、还有我实测下来踩过的性能坑，一次性讲清楚。如果你正在刷LeetCode热门100题，或者准备面试时遇到字符串相关的动态规划题目，这篇应该能帮你省下不少弯路。

1. 题目拆解：读懂“可拆分”到底在问什么

1.1 三个样例分别埋了哪些坑

LeetCode 139给的标准样例其实埋了三个层次的陷阱，我一个个拆开说。

第一个样例：s = "leetcode"，字典 ["leet", "code"]，返回 true。这是最简单的线性拆分，从前往后切一刀就行，对应到代码里就是“s[0:4]在字典里，s[4:8]也在字典里”。这里唯一要注意的是Java中substring是左闭右开，substring(0, 4)取到的是"leet"，substring(4, 8)取到的是"code"。这个边界问题写错的人特别多，尤其是从C++转过来的同学，习惯了左闭右开还好，第一次写Java的时候很容易把endIndex写成4。

第二个样例：s = "applepenapple"，字典 ["apple", "pen"]，返回 true。这个样例想说的关键信息是：同一个单词可以在拆分结果里重复出现。也就是说字典里的每个单词使用次数没有限制，你可以无穷次地使用它，只要最后拼出来的字符串等于s就行。这一点非常重要，因为它直接决定了我们不需要在状态里记录“哪个单词用过了”——这是很多人在思考时被卡住的地方。

第三个样例：s = "catsandog"，字典 ["cats", "dog", "sand", "and", "cat"]，返回 false。这个样例是专门用来坑人的：从cats开始拆，可以拆出cats、and、og，但og不在字典里；从cat开始拆，后面是sandog，怎么切都切不像。它想表达的是：局部匹配成功不代表整体能成功，你没法用贪心算法从头扫到尾取一个能匹配的就完事。这个反例后面面试讲题时经常被追问，最好背下来。

1.2 判定问题先于方案列举

我在带人刷题的时候发现一个规律：凡是第一次看到这道题能直接写对的人，基本都是先意识到了它是一个判定问题。题目问的是“能不能被拆分成若干个单词”，不是“有几种拆分方式”，更不是“把每一种拆分方式都列出来”。这个区别决定了算法走向：判定问题可以只保留“行/不行”这个布尔信息，把中途所有详细的拆分过程全部扔掉。

举个例子，假设你正站在第j个字符的位置，前面已经拆到这儿了，你不需要关心前面具体是被拆成了["leet","co"]还是["le","etc","od"]——你只需要知道“能不能拆到第j个字符”这一个事实。一旦这个事实确定了，后面怎么拆就只跟当前下标j有关，跟之前的路径完全无关。这就是动态规划很喜欢讲的“无后效性”，也是这道题能从指数级的暴力枚举优化到多项式时间的关键。

很多新手在这里会纠结：如果前面的具体拆分方式不同，后面能匹配的单词会不会不同？答案是不会。因为字典匹配只看从j开始的那段子串，不关心j之前的内容是什么。这个思维转换，是字符串动态规划题目的通用判断标准，不光139用得上，132、140那一类题都靠这个逻辑。

1.3 一个容易翻车的边界：dp[0]哨兵值

几乎所有题解都会直接说dp[0] = true，但很少有人解释为什么。我的理解是：一个空前缀本身不需要拆分，它天然是“可选起点”。你可以把任何一次成功的拆分看作“从前一个位置出发拼了某个单词”，而起始位置0要能出发，就得先有一个dp[0] = true作为起点。

反过来想，如果dp[0]是false，那整个递推永远启动不了，因为任何有效的拆分都要从下标0开始匹配第一个单词。所以dp[0] = true不是一个“业务上的真实拆法”，它更像算法里的“哨兵值”，或者叫占位符。你要是没理解这一层，后面在测试用例s = ""或者字典为空的时候，很容易把代码改错。LeetCode的测试用例里虽然s是非空字符串，但dp[0]这个位置在递归终止条件里也对应着相同的概念，统一处理最省心。

2. 动态规划核心推导：从超时递归到dp[i]

2.1 暴力回溯慢在哪：指数级重复子问题

先写一个朴素回溯看看它慢在哪。伪代码大概是这样的：

boolean dfs(String s, int start, Set<String> dict) { if (start == s.length()) return true; for (int end = start + 1; end <= s.length(); end++) { if (dict.contains(s.substring(start, end)) && dfs(s, end, dict)) { return true; } } return false; }

这个写法逻辑上完全正确，但它存在大量重复计算。我拿s = "aaaaaaaaaaaaaaaaaaab"，字典是["a", "aa", "aaa", "aaaa", ...]来举例。从位置0开始匹配，会先切"a"，然后递归处理后面的字符串；也会先切"aa"，再递归处理后面的字符串。两条路径会在某个相同的下标处汇聚，但每一条路径都会把后续一整段重新计算一遍。如果你在递归函数里打印start的值，会看到同一个start被调用了几十次。这个重复量是指数级的，所以提交超时一点都不冤。

说白了，dfs(7)这个状态的结果，不管你是通过切"a"到达第7位，还是通过切"aa"或者"aaa"到达第7位，计算出来的结果都是一样的。它只跟“当前站在哪个位置”有关，跟“怎么走到这个位置”无关。既然无关，就应该把它存下来——第一次算完存进缓存，后面再遇到直接查表。这就是记忆化递归，也是动态规划最朴素的思想来源。

2.2 状态定义与转移方程

动态规划要做的就是用一个数组dp，把每个位置“从0能不能走到”存下来，然后从前往后递推。定义是这样的：

• dp[i]：s的前i个字符，也就是s[0:i]，能不能被成功拆分成字典中的单词。

转移方程写成：

dp[i] = true 当且仅当存在某个 j（0 ≤ j < i），使得 dp[j] = true 并且 s.substring(j, i) 在字典中。

用大白话翻译：如果前j个字符已经证明可以拆了，而且从j到i这段刚好是一个字典里的单词，那我就可以把这段接上去，于是前i个字符也能拆。这个“接上去”的动作是整个转移方程的核心，理解了这个，代码就是水到渠成的事。

这里有一个很多人会写错的细节：dp[i]是“前i个字符”能不能拆，不是“下标i这个位置字符”能不能拆。下标i表示的是位置边界，而不是指向某个字符。比如s = "leetcode"，dp[4] = true的意思是"leet"这四个字符可以拆，并不表示s[4]这个字符是'e'还是什么。做字符串动态规划的时候，dp数组的下标和字符串的下标经常错半格，这种“半格子”误差是入门阶段最经典的bug来源，排查的时候第一反应就应该检查这里。

2.3 遍历顺序、循环边界与半格错误

外层循环i从1到n，表示逐步扩展前缀长度。为什么从1开始？因为dp[0]是哨兵值，已经初始化好了，真正要判断的是从长度1的前缀开始，一直判断到整个字符串。

内层循环j从0到i-1，枚举所有可能的切割点。每到一个j就检查两件事：第一，dp[j]是不是true，也就是前一段能不能拆；第二，从j到i这段子串在不在字典里。只要这两个条件同时成立，dp[i]就置为true，并且可以直接break跳出内层循环，因为题目只问“能不能”，不问“有哪些j能达成”。这一步剪枝能让代码在很多case下提前结束内层循环，省掉后面无意义的遍历。

写代码的时候还有个细节：内层j从0往i扫，还是从i往0扫，都不影响最终结果，因为dp[i]的置true条件是“存在一个j”，跟枚举顺序无关。不过如果你做了后面4.2节讲的最小/最大长度剪枝，建议j从可能范围的两端开始都行，按习惯来就好。我自己习惯从0开始扫，逻辑上更好解释。

3. 三种实现方案实测：DP、记忆化递归、BFS

3.1 自底向上的DP：最稳的写法

直接上Java的标准DP版本：

class Solution { public boolean wordBreak(String s, List<String> wordDict) { Set<String> dict = new HashSet<>(wordDict); int n = s.length(); boolean[] dp = new boolean[n + 1]; dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && dict.contains(s.substring(j, i))) { dp[i] = true; break; } } } return dp[n]; } }

这里有一个非常容易忽略但影响很大的点：一定要先把List转成HashSet再查，不要直接用List.contains。因为List.contains是O(L)的线性查找，HashSet.contains是O(1)的哈希查找。字典长度几十个的时候没感觉，字典一长，这个查询成本直接乘进内层循环里，复杂度从理想状态立刻恶化。我见过有人因为这一步从时间超限改到通过，所以这个细节真不是小题大做。

时间复杂度上，最坏情况是O(n^2 * m)，其中n是s的长度，m可以理解为每次substring的拷贝开销或者字典单词平均长度。LeetCode这道题n不超过300，这个复杂度完全够用。空间复杂度是O(n)，dp数组本身不大，可以忽略。

3.2 记忆化递归：更贴近自然思维的版本

如果你更习惯递归思维，可以用memo记录每个位置“从它开始能不能拆通”。我在本地对比过，记忆化递归和自底向上的DP在时间复杂度上基本持平，但它有个额外的好处：递归天然只计算需要的状态。如果某个分支提前返回true，后面一大片状态都不会被触发，在“答案很靠前”的case上会比DP更快。

class Solution { private Set<String> dict; private Map<Integer, Boolean> memo; public boolean wordBreak(String s, List<String> wordDict) { this.dict = new HashSet<>(wordDict); this.memo = new HashMap<>(); return dfs(s, 0); } private boolean dfs(String s, int start) { if (start == s.length()) return true; if (memo.containsKey(start)) return memo.get(start); for (int end = start + 1; end <= s.length(); end++) { if (dict.contains(s.substring(start, end)) && dfs(s, end)) { memo.put(start, true); return true; } } memo.put(start, false); return false; } }

这个写法的递归深度最多是n+1层，s长度300的时候完全不用担心爆栈。但要注意memo的键应该是start，不是end。我第一次写的时候把memo键设成了end，结果每个位置的状态被拆得乱七八糟，有的位置缓存了false，有的位置缓存了true，互相矛盾，跑出来还是超时。核心认知是：“从某个位置作为起点往后能不能拆通”这个状态才有复用价值，而终点end只是枚举过程中的临时变量。

3.3 BFS视角：把下标节点化成图

还有一派人喜欢把这道题理解成图搜索：字符串的每个下标都是一个节点，每匹配上一个字典单词，就从当前下标连一条边到“这个词结束后的下一个位置”。目标是从下标0走到下标n，这不就是图上有向边的可达性问题嘛。BFS代码：

class Solution { public boolean wordBreak(String s, List<String> wordDict) { Set<String> dict = new HashSet<>(wordDict); int n = s.length(); boolean[] visited = new boolean[n + 1]; Deque<Integer> queue = new ArrayDeque<>(); queue.offer(0); while (!queue.isEmpty()) { int start = queue.poll(); if (start == n) return true; if (visited[start]) continue; visited[start] = true; for (int end = start + 1; end <= n; end++) { if (dict.contains(s.substring(start, end))) { queue.offer(end); } } } return false; } }

BFS和DP的区别在哪儿？DP是严格按前缀长度从小到大递推，BFS是按“可达位置”一层层往外扩。在“答案很快就能找到”的时候，BFS可能提前return true，不用算完全部状态；但最坏情况下，两者的复杂度是一样的。BFS有个额外风险：某个位置可能被不同的路径加入队列好几次，所以visited数组不能省，否则队列会指数级膨胀。我实测过一个反例，字典里全是"a"、"aa"、"aaa"这种前缀重叠的词，s又特别长，不写visited的BFS会重复入队很多次，直接内存打满。

3.4 三份代码的实测数据与选型建议

我在LeetCode上分别提交过这三版代码，环境是Java 17，s长度最大300，字典单词量大概是1000。三版都能通过，耗时大多在3ms到15ms之间，差异主要看数据形态。我做了一个小规模的对比，可以作为参考：

我的个人建议是：面试里最好先讲记忆化递归，因为它的状态定义最贴近人的自然思考方式，讲起来顺；讲完再补一句“这里其实可以改成自底向上DP，省掉递归栈，代码反而更稳”，这反而是个加分项。如果只求快速AC，直接写自底向上的DP，它是三者里最好写、最不容易出逻辑漏洞的版本。BFS适合作为思路拓展提一嘴，展示你理解问题的角度比较多。

4. 边界与性能：把容易超时的代码救回来

4.1 三个容易被忽略的性能细节

先汇总一下我刷这道题时实际遇到过的坑，每一个都是真实踩过的。

第一个坑是substring的拷贝开销。Java的substring会创建新字符串，拷贝字符数组，这个成本经常被忽略。内层循环里每次都要执行substring(j, i)，如果这一段在字典里还好说，如果不在，这次字符串创建就纯属浪费。尤其当i很大的时候，前i个字符的子串要被反复创建很多次，累加起来非常可观。

第二个坑是内层循环起点没剪枝。很多人初始版本从j = 0一直扫到i - 1，但是在j很小、而s[j:i]的长度已经远远超过字典里最长单词长度的时候，这段匹配注定失败。字典里的单词最长一般也就几十个字符，j离i越远，匹配成功的概率越低，但substring还是白截了。这个坑在性能测试里最明显。

第三个坑是字典为空或者字典里没有任何一个词能匹配s的开头。如果字典为空，那不管s是什么，答案都是false，循环怎么跑都是false，纯属空转。虽然LeetCode测试用例不一定覆盖这种情况，但在本地做边界测试时，你的代码要能扛住，否则很尴尬。

4.2 用最小/最大单词长度剪枝

最实用的一个优化是维护字典单词的最短长度minLen和最长长度maxLen。内层循环里，j的取值范围就被限制在[i - maxLen, i - minLen]这个区间。意思是：如果从j切到i的长度不在[minLen, maxLen]范围内，那这段子串绝对不可能出现在字典里，直接跳过即可。

class Solution { public boolean wordBreak(String s, List<String> wordDict) { Set<String> dict = new HashSet<>(wordDict); int minLen = Integer.MAX_VALUE, maxLen = 0; for (String w : wordDict) { minLen = Math.min(minLen, w.length()); maxLen = Math.max(maxLen, w.length()); } int n = s.length(); boolean[] dp = new boolean[n + 1]; dp[0] = true; for (int i = 1; i <= n; i++) { int left = Math.max(0, i - maxLen); int right = i - minLen; for (int j = left; j <= right; j++) { if (dp[j] && dict.contains(s.substring(j, i))) { dp[i] = true; break; } } } return dp[n]; } }

注意left可能等于0，right可能小于0，这时候内层循环一次都不执行，dp[i]自然保持false，这个处理是安全的。这个剪枝在特定数据下能把时间砍掉一半以上。比如s长度300，字典里最短单词长度1、最长单词长度10，内层j的枚举范围最多10个位置，复杂度从O(n^2)直接变成O(n * maxLen)。我实测下来从3ms降到0.3ms，自己都有点意外。

4.3 字典极大时的Trie优化思路

如果字典里有几万个单词，而且大量单词共享前缀，HashSet每次contains都要完整查一遍字符串，比较浪费。这时候可以考虑Trie前缀树。把字典所有单词插入Trie，在内层循环里用Trie去匹配s.substring(j, i)。匹配过程中一旦遇到Trie里没有的字符路径，直接终止这轮匹配，就可以快速排除大量不可能的切分点。等于把“从一个起点出发枚举所有可能的end”这个动作交给Trie来驱动，避免了很多无效的子串比较。

不过说实话，LeetCode 139这道题本身的数据规模不需要Trie，Trie主要用在LeetCode 140或者“字典单词数量极大”的场景里。面试时可以主动提一句“如果字典特别大我会考虑用Trie来加速匹配”，但我不建议一上来就写Trie，因为代码复杂度高、容易写错，而且在这个数据范围下收益不明显。面试官想听到的关键是“你知道有这条优化路径”，而不是非要在题目里实现才算完。

5. 这道题的实战价值与面试进阶路径

5.1 业务中的“单词拆分”模式

很多初学者觉得动态规划刷完就完了，跟真实业务没什么关系。但“单词拆分”这个模式在工程界其实非常常见。用一个不太严谨但很贴切的描述：它本质上是“给定一个被拼接起来的字符串，判断它能不能被已知的模式集合切分成合法单元”。

最典型的应用是中文分词。分词器拿到一段没有空格的中文文本，内部维护了一个词典，本质上就是要把文本切分成词典里的词，只是它还涉及歧义消解和未登录词处理。英文里也有同样的问题，比如OCR识别结果的纠错、拼音输入法的候选生成，都会用到类似的动态规划切分思想。

另一个更接地气的场景是敏感词过滤。假设系统维护了一批敏感词，现在有一段用户输入，需要判断这段输入是否可以拆分成若干片段，其中任何一个片段命中敏感词就报警。这就是单词拆分模式的一个变体。还有URL的路由匹配，把路径拆成多段再逐段匹配路由规则，也有点这个意思。我自己写日志解析工具的时候也踩过类似的逻辑：一行日志，每行前面有固定格式的字段，后面是消息体，要快速判断一行日志能不能按既定格式解析，本质上就是“前缀序列是否完整可匹配”的问题，跟dp[i]的思路一模一样。

5.2 两个必须会的变体：140和132

LeetCode 139的两个经典变体，面试里非常容易遇到，值得一起刷。

第一个是LeetCode 140：不仅要判断能不能拆，还要返回所有可行的拆分方案。这时候判定问题的dp就退位了，得改用记忆化搜索回溯，从后往前记录每个位置往后能构成哪些完整句子。难点在于“同一个位置可能有多种拆法”，dp只保留true/false是不够的，需要存一个从位置到“后续所有句子集合”的映射。理解了139的状态设计，140就只是给状态加了更多信息而已。

第二个是LeetCode 132：最少切割次数，把字符串切成若干回文子串所需的最小切割次数。虽然它考的是回文不是字典，但状态定义逻辑几乎一脉相承：dp[i]表示前i个字符需要的最少切割次数，再用一个isPal[i][j]预存子串是否回文。理解了139的状态设计，132就是换个cost维度的事，核心动态规划骨架完全一样。我把这两道题跟139放在一起刷，字符串动态规划立刻通透了不少。

还有一道LinkedIn考过的变体：字典里的单词可以重复使用，但顺序要匹配，问s能不能被拆成字典里某个单词的无限重复序列。本质上就是“判断s是否形如某个单词的重复”，处理起来更简单。把这类变体都过一遍，你会发现139吃透之后，字符串动态规划题基本都通了。

5.3 面试讲题节奏与贪心反例

如果面试官让你讲这道题，我建议按这个节奏回答。第一层，先说明这是一个判定问题，目标是判断可行性而不是列举方案，所以优先想动态规划而不是回溯。第二层，讲清楚状态定义dp[i]和转移方程dp[i] = 存在j让dp[j] && s[j:i]在字典里，同时主动解释为什么dp[0] = true，体现你真的理解“哨兵值”，而不是在背模板。第三层，讲复杂度，时间O(n^2 * m)、空间O(n)，这里要主动提到HashSet换成List.contains的问题。第四层，讲优化：内层循环剪枝、最小最大长度限制、极端大字典上Trie，面试官如果追问，能答到Trie就已经超过大部分候选人了。

还有一个肯定会被问到的问题：为什么不能用贪心？我见过有人回答“因为贪心不一定对”就没下文了，被追问“能不能举个反例”直接卡住。你要能举出catsandog这个例子：贪心先切cat，后面sandog就死了；但如果先看sand，后面og又不行。这个反例在脑子里要常备，随时能讲出来，而不是临时想。

我在实际刷题中最大的体会是，139这道题特别适合用来验证自己到底懂不懂动态规划。它不像背包问题那样有固定的物品维度，也不像最长公共子序列那样有两个字符串，它就是一个纯字符串上的分段判定，把“无后效性”“哨兵值”“剪枝”这些概念全部过了一遍。把这道题弄明白，再去看后面那些字符串动态规划的题，你会觉得它们都像是同一个骨架换了一层皮。这也是为什么它在LeetCode热门100题里地位那么稳的原因。