当前位置：首页 > news >正文

LeetCode 139. 单词拆分：动态规划经典入门题

news 2026/4/19 19:54:22

LeetCode中等难度的经典题——139. 单词拆分，这道题是动态规划的入门必练题目，核心考察“子问题拆解”和“状态转移”的思路，而且代码不长，吃透思路后能快速掌握动态规划的基础逻辑，新手也能轻松上手。

一、题目解读：读懂题意，找对方向

先看题目描述，避免理解偏差：

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

关键注意点（划重点，避坑关键）：

不要求字典中所有单词都使用，用其中一部分即可；
字典中的单词可以重复使用（比如字典有“a”，可以用多次“a”拼接出“aaa”）；
拼接时，单词之间不能有多余字符，必须完全覆盖字符串 s（比如 s 是“applepen”，字典有“apple”和“pen”，拼接后正好是 s，返回true；如果字典有“app”“lepen”，也可以）。

二、解题思路：为什么用动态规划？

拿到这道题，首先会想到“暴力枚举”——遍历所有可能的单词组合，看是否能拼出s。但暴力解法的时间复杂度极高（指数级），比如s很长、字典单词很多时，会直接超时，所以必须找更高效的方法。

这时候就该动态规划登场了！动态规划的核心是“将大问题拆成小问题，用小问题的答案推导出大问题的答案”，这道题正好符合这个特点：

大问题：字符串s[0..n-1]（n是s的长度）能否被字典单词拼接；

小问题：字符串s[0..i-1]（i从1到n）能否被拼接；

只要我们能求出所有小问题的答案，最终就能得到大问题的答案（也就是s[0..n-1]的拼接结果）。

三、动态规划核心拆解（图文思路，一看就懂）

1. 定义DP数组

我们定义 dp[i] 表示：字符串 s 的前 i 个字符（即 s[0..i-1]）能否被字典中的单词拼接而成。

比如 dp[0] 表示“空字符串”，空字符串不需要任何单词拼接，所以 dp[0] = true（这是我们的初始条件，也是整个DP的基础）；dp[3] 就表示 s 的前3个字符（s[0]、s[1]、s[2]）能否被拼接。

2. 确定状态转移方程

如何从 dp[j] 推导出 dp[i]？（j < i）

假设我们现在要判断 dp[i] 是否为 true，我们可以遍历所有 j（从0到i-1），只要满足两个条件，dp[i] 就为 true：

dp[j] 为 true：表示 s 的前 j 个字符能被拼接（小问题已解决）；
s 从 j 到 i 的子串（s.substring(j, i)）存在于字典中：表示从 j 到 i 的这部分字符，正好是字典中的一个单词。

简单说就是：前 j 个字符能拼出来，且 j 到 i 的字符是字典里的单词，那么前 i 个字符就能拼出来。

状态转移方程可简化为：dp[i] = dp[j] && wordSet.has(s.substring(j, i))（只要找到一个满足条件的 j，就可以确定 dp[i] = true，跳出循环）。

3. 初始化与遍历顺序

初始化：dp[0] = true（空字符串可拼接），其余 dp[1..n] 初始化为 false（默认不能拼接）。

遍历顺序：外层循环遍历 i（从1到n，对应前1个、前2个…前n个字符），内层循环遍历 j（从0到i-1，遍历所有可能的拆分点），这样就能保证在计算 dp[i] 时，所有 dp[j]（j < i）都已经计算完成。

4. 优化：用Set提升查询效率

题目给出的 wordDict 是列表，列表的 has 操作时间复杂度是 O(k)（k是列表长度），如果把 wordDict 转换成 Set，查询时间复杂度就能降到 O(1)，能明显提升代码运行效率——这是一个小优化，也是实际刷题中常用的技巧。

四、完整代码+逐行注释

结合上面的思路，给出完整的TypeScript代码，每一行都加了注释，新手也能看懂：

functionwordBreak(s:string,wordDict:string[]):boolean{constn=s.length;// 1. 获取字符串s的长度constwordSet=newSet(wordDict);// 2. 转换为Set，提升查询效率constdp=newArray(n+1).fill(false);// 3. 初始化DP数组，dp[i]表示前i个字符能否拼接dp[0]=true;// 4. 初始条件：空字符串可拼接// 5. 外层循环：遍历前i个字符（i从1到n）for(leti=1;i<=n;i++){// 6. 内层循环：遍历所有可能的拆分点j（从0到i-1）for(letj=0;j<i;j++){// 7. 状态转移：前j个能拼，且j到i的子串在字典中 → 前i个能拼if(dp[j]&&wordSet.has(s.substring(j,i))){dp[i]=true;break;// 找到一个满足条件的j，无需继续遍历j}}}returndp[n];// 8. 返回前n个字符（即整个s）能否拼接的结果};

五、代码运行示例（直观理解）

以 s = ‘leetcode’，wordDict = [‘leet’,‘code’] 为例，看DP数组的变化过程：

n = 8，dp数组初始为 [true, false, false, false, false, false, false, false, false]
i=1：j从0到0 → s.substring(0,1)是“l”，不在字典，dp[1]仍为false；
i=2：j从0到1 → 所有子串（“le”“e”）都不在字典，dp[2] false；
i=3：j从0到2 → 子串都不在字典，dp[3] false；
i=4：j=0时，s.substring(0,4)是“leet”，在字典，且dp[0] = true → dp[4] = true；
i=5：j遍历0-4，只有j=4时，s.substring(4,5)是“c”，不在字典 → dp[5] false；
…以此类推，直到i=8：j=4时，s.substring(4,8)是“code”，在字典，且dp[4] = true → dp[8] = true，最终返回true。

六、常见坑点 & 优化建议

常见坑点

忘记初始化 dp[0] = true：这是整个DP的基础，没有这个初始条件，所有子问题都无法推导，最终会返回false；
内层循环没有break：找到一个满足条件的j后，就可以确定dp[i] = true，继续遍历j只会浪费时间；
没有用Set优化：当wordDict长度很大时，列表查询会超时，一定要转换成Set。

优化建议

如果字符串s很长（比如长度1000+），可以再增加一个优化：内层循环j的范围可以限制在“i - maxWordLength”到i-1，其中maxWordLength是字典中最长单词的长度。因为如果j太小，s.substring(j,i)的长度超过了字典中最长单词，就不可能在字典中，这样可以减少内层循环的次数，提升效率。

比如字典中最长单词是4个字符，那么i=8时，j只需从4到7遍历（8-4=4），无需从0到7，能节省一半的遍历时间。