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

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 lt; i假设我们现在要判断 dp[i] 是否为 true我们可以遍历所有 j从0到i-1只要满足两个条件dp[i] 就为 truedp[j] 为 true表示 s 的前 j 个字符能被拼接小问题已解决s 从 j 到 i 的子串s.substring(j, i)存在于字典中表示从 j 到 i 的这部分字符正好是字典中的一个单词。简单说就是前 j 个字符能拼出来且 j 到 i 的字符是字典里的单词那么前 i 个字符就能拼出来。状态转移方程可简化为dp[i] dp[j] amp;amp; 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 lt; i都已经计算完成。4. 优化用Set提升查询效率题目给出的 wordDict 是列表列表的 has 操作时间复杂度是 O(k)k是列表长度如果把 wordDict 转换成 Set查询时间复杂度就能降到 O(1)能明显提升代码运行效率——这是一个小优化也是实际刷题中常用的技巧。四、完整代码逐行注释结合上面的思路给出完整的TypeScript代码每一行都加了注释新手也能看懂functionwordBreak(s:string,wordDict:string[]):boolean{constns.length;// 1. 获取字符串s的长度constwordSetnewSet(wordDict);// 2. 转换为Set提升查询效率constdpnewArray(n1).fill(false);// 3. 初始化DP数组dp[i]表示前i个字符能否拼接dp[0]true;// 4. 初始条件空字符串可拼接// 5. 外层循环遍历前i个字符i从1到nfor(leti1;in;i){// 6. 内层循环遍历所有可能的拆分点j从0到i-1for(letj0;ji;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 8dp数组初始为 [true, false, false, false, false, false, false, false, false]i1j从0到0 → s.substring(0,1)是“l”不在字典dp[1]仍为falsei2j从0到1 → 所有子串“le”“e”都不在字典dp[2] falsei3j从0到2 → 子串都不在字典dp[3] falsei4j0时s.substring(0,4)是“leet”在字典且dp[0] true → dp[4] truei5j遍历0-4只有j4时s.substring(4,5)是“c”不在字典 → dp[5] false…以此类推直到i8j4时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个字符那么i8时j只需从4到7遍历8-44无需从0到7能节省一半的遍历时间。七、总结这道题的核心价值139.单词拆分是动态规划的“入门敲门砖”它的核心思路——“拆分问题状态转移”适用于很多类似的“拼接”“组合”问题。做完这道题后你可以重点掌握如何定义DP数组贴合题目场景将大问题拆成小问题如何推导状态转移方程找到小问题和大问题的关联常用的优化技巧Set提升查询效率、限制循环范围。