文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接139.单词拆分2、题目描述二、个人思路整理1、思路分析核心思路完全背包问题字典中的单词可以重复选取拼接成目标串s ss状态定义定义布尔数组dp[i]表示字符串s ss的前i ii个字符组成的子串s [ 0 … i − 1 ] s[0 \dots i-1]s[0…i−1]是否能够被字典中的单词拆分/拼接。边界条件dp[0] true空字符串默认合法作为递推基准。状态转移方程对于长度为i ii的前缀子串枚举分割点j jj(0 ≤ j i 0 \le j i0≤ji)dp [ i ] dp [ i ] ∨ ( dp [ j ] ∧ ( s [ j … i − 1 ] ∈ wordDict ) ) \text{dp}[i] \text{dp}[i] \lor (\text{dp}[j] \land (s[j \dots i-1] \in \text{wordDict}))dp[i]dp[i]∨(dp[j]∧(s[j…i−1]∈wordDict))只要找到任意一个切分点j jj使得前半部分s [ 0 … j − 1 ] s[0 \dots j-1]s[0…j−1]可拆分即dp[j] true且后半部分子串s [ j … i − 1 ] s[j \dots i-1]s[j…i−1]存在于字典中那么dp[i]即为true可直接break提前结束内层循环。优化细节哈希集合加速查询把wordDict存入unordered_setstring子串匹配时可以在O ( L ) O(L)O(L)时间内判断是否存在L LL为子串长度。长度剪枝字典中单词的最大长度为 20提示中给出wordDict[i].length 20。因此内层枚举j jj时只需要从i − 1 i - 1i−1倒序枚举到max ⁡ ( 0 , i − maxLen ) \max(0, i - \text{maxLen})max(0,i−maxLen)避免不必要的子串截取。2、解题代码classSolution{public:boolwordBreak(string s,vectorstringwordDict){// 1. 使用哈希集合存储词典单词将查找时间优化至平均 O(L)// 同时记录字典中最长单词长度用于后续剪枝unordered_setstringdict;intmax_len0;for(conststringw:wordDict){dict.insert(w);max_lenmax(max_len,(int)w.size());}intns.size();// 2. dp[i] 表示字符串 s 的前 i 个字符 s[0...i-1] 是否能被字典拆分vectorbooldp(n1,false);// 空字符串作为基本状态合法可拆分dp[0]true;// 3. 动态规划填表外层遍历前缀子串的长度 ifor(inti1;in;i){// 内层枚举分割点 j// 从离 i 最近的位置开始向左枚举由于单词最大长度为 max_len// 超出 max_len 的子串无需检验直接剪枝for(intji-1;jmax(0,i-max_len);j--){// 如果前半部分 s[0...j-1] 可拆分dp[j] 为 true// 且后半部分 s[j...i-1] 存在于字典汇总则 s[0...i-1] 整体可拆分if(dp[j]dict.count(s.substr(j,i-j))){dp[i]true;break;// 只要找到一种有效切分方式即可提前退出内层循环}}}// 4. 返回整个字符串 s 的拆分结果returndp[n];}};复杂度分析时间复杂度O ( n ⋅ L 2 ) O(n \cdot L^2)O(n⋅L2)。其中n nn是字符串s ss的长度L LL是字典中最长单词的长度本题中L ≤ 20 L \le 20L≤20。外层循环n nn次内层最多循环L LL次每次截取子串并哈希比较耗时O ( L ) O(L)O(L)。空间复杂度O ( n M ) O(n M)O(nM)其中M MM为字典中所有字符的总数哈希表开销n nn为 dp 数组的大小。三、知识风暴动态规划Dynamic Programming是本题的核心算法思想。它通过将原问题拆解为若干重叠子问题并利用「最优子结构」性质用子问题的最优解递推得到全局最优解。对于「单词拆分」这类具有明显递推关系的问题动态规划能以O ( n ⋅ L 2 ) O(n \cdot L^2)O(n⋅L2)的复杂度高效求解。算法核心思想最优子结构字符串s ss的前i ii个字符能否被拆分可以由「前j jj个字符能否被拆分」与「子串s [ j … i − 1 ] s[j \dots i-1]s[j…i−1]是否在字典中」共同决定。只要子问题d p [ j ] dp[j]dp[j]为真且后半段子串命中字典那么d p [ i ] dp[i]dp[i]也一定为真。重叠子问题在递推过程中较小的d p dpdp值会被反复使用。例如计算d p [ 10 ] dp[10]dp[10]和d p [ 13 ] dp[13]dp[13]时都可能用到d p [ 9 ] dp[9]dp[9]因此用布尔数组缓存结果可避免重复计算。与贪心的区别贪心每一步只做当前最优选择、不回溯而动态规划会枚举所有可能的分割点j jj只要找到任意一种合法切分即判定可拆分从而保证结果的正确性。常见对比动态规划 vs 贪心动态规划时间复杂度O ( n ⋅ L 2 ) O(n \cdot L^2)O(n⋅L2)空间复杂度O ( n M ) O(n M)O(nM)M MM为字典字符总数。适合需要枚举所有子问题、且局部最优不能直接决定全局最优的场景通用性更强。贪心算法时间复杂度O ( n ⋅ L ) O(n \cdot L)O(n⋅L)需先对字典建哈希表空间复杂度O ( M ) O(M)O(M)。适合每一步的局部最优能直接推导全局最优的场景代码简洁高效但本题无法直接证明贪心成立如s applepenapple若贪心先匹配apple后剩余penapple无法匹配而实际存在合法拆分。共同点两者都依赖「最优子结构」性质。区别在于贪心只保留一个当前最优状态而动态规划需要维护一张状态表。动态规划的设计思想核心思想把大问题拆成小问题先解决小问题再用小问题的答案拼出大问题的答案。本题中先求出d p [ 0 ] , d p [ 1 ] , … , d p [ n − 1 ] dp[0], dp[1], \dots, dp[n-1]dp[0],dp[1],…,dp[n−1]再逐个递推出d p [ n ] dp[n]dp[n]。与本题的联系单词拆分问题天然具有递推结构——每个前缀长度i ii都可以由某个更小的前缀长度j jj加上一个字典中的单词得到。因此无需回溯或搜索只需按顺序填表即可。注意事项动态规划的正确性依赖于「最优子结构」与「无后效性」。本题中d p [ i ] dp[i]dp[i]只由更小的d p dpdp值决定与未来的状态无关因此递推顺序合法。使用要点状态数组dp[i]记录字符串s ss的前i ii个字符s [ 0 … i − 1 ] s[0 \dots i-1]s[0…i−1]是否能被字典拆分长度为n 1 n1n1。初始化dp[0] true空字符串默认合法作为递推基准。转移时机外层循环遍历i ii从1 11到n nn内层循环枚举分割点j jj从i − 1 i-1i−1倒序到max ⁡ ( 0 , i − maxLen ) \max(0, i - \text{maxLen})max(0,i−maxLen)执行dp[i] dp[i] || (dp[j] dict.count(s.substr(j, i - j)))。结果返回遍历结束后返回dp[n]表示整个字符串s ss是否可被字典拆分。算法变体与扩展完全平方数LeetCode 279同样是「完全背包 最少数量」的经典题目物品从字典单词换成完全平方数思路完全一致。组合总和 ⅣLeetCode 377同样是「完全背包」问题但求的是方案总数而非可行性判断转移方程略有不同。一和零LeetCode 474二维费用的 0-1 背包问题与本题共享「背包 动态规划」的核心模式。零钱兑换 IILeetCode 518同样是「完全背包」问题但求的是凑成目标金额的方案总数与本题的「可行性判断」形成对比。相关 LeetCode 例题279. 完全平方数完全背包 最少数量377. 组合总和 Ⅳ完全背包 方案计数474. 一和零二维费用背包518. 零钱兑换 II完全背包 方案计数