LeetCode 139. 单词拆分Word Break题解从暴力匹配到记忆化递归与动态规划【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文基于 leetcode 题解仓库中的 139. 单词拆分题解完整讲解 LeetCode 139 题Word Break的解题全路径从可被接受的暴力匹配到借助「子问题规模缩小、性质不变」这一观察引入的记忆化递归再到用哈希集合枚举切分点、使复杂度与字典大小解耦的最终优化方案。读完本文你将掌握「字符串拼接判定」类问题的动态规划建模思路、记忆化递归与自底向上 DP 的等价转换以及如何用 Python3 / JavaScript / C 三语言落地实现。题目描述给定一个非空字符串s和一个包含非空单词的列表wordDict判定s是否可以被空格拆分为一个或多个在字典中出现的单词。说明拆分时可以重复使用字典中的单词可以假设字典中没有重复的单词。三个官方示例示例 1 输入: s leetcode, wordDict [leet, code] 输出: true 解释: 返回 true 因为 leetcode 可以被拆分成 leet code。 示例 2 输入: s applepenapple, wordDict [apple, pen] 输出: true 解释: 返回 true 因为 applepenapple 可以被拆分成 apple pen apple。 注意你可以重复使用字典中的单词。 示例 3 输入: s catsandog, wordDict [cats, dog, sand, and, cat] 输出: false示例 3 是一个很好的反例catsandog虽然能以多种前缀组合cats、cat、sand、and切分但剩余部分无法再由字典中的单词覆盖因此整体不可拆分。前置知识本题在仓库中被归类于两类核心套路之下建议先阅读对应讲义动态规划本题是「记忆化递归 → 自底向上 DP」转换的典型练习仓库的 DP 讲义专门将其列为推荐练习题目见 thinkings/dynamic-programming.md#L914-L925与 91.decode-ways、198.house-robber、322.coin-change、416.partition-equal-subset-sum、518.coin-change-2 等共同构成入门练习清单字符串问题仓库将 139 归入字符串专题的「其他问题」分类见 thinkings/string-problems.md#L49与之相关的还有 208.implement-trie-prefix-tree 等前缀树题目回溯若需要输出全部拆分方案而非仅判定可行则会用到回溯与记忆化参见进阶题 140. 单词拆分 II。思路一暴力匹配可行但昂贵这道题本质是给定一个字典和一个句子判断句子是否可以由字典中的单词拼出来且一个单词可以用多次。最直观的暴力思路是从匹配位置 0 开始在wordDict中逐个尝试只要某个单词能和s的当前位置匹配上就更新匹配位置继续匹配。以s leetcode、wordDict [leet, code]为例先试试leet可以匹配吗可以。匹配后s剩下code继续在wordDict中找再试leet可以匹配吗不能。code能够匹配吗可以。返回true结束。如果wordDict遍历一次后匹配位置没有任何进展说明从当前位置无法继续直接返回false。暴力法的缺陷在于一旦某条匹配路径走不通回溯时会反复尝试大量重复的子问题。比如对s aaaa...ab长串a结尾一个b、wordDict [a, aa, aaa, ...]这类输入同一后缀会被从不同前缀路径反复计算导致指数级复杂度。思路二记忆化递归 —— 抓住子问题性质暴力匹配过程有一个关键观察匹配成功一次后本质上只是把问题规模缩小了而问题性质不变——剩下的字符串能否被字典拆分依然是一个相同的判定问题。因此可以用动态规划/记忆化递归来消除重复计算。令dp(pos)表示「s[pos:]能否被字典拆分」则有边界条件pos len(s)时空串一定可拆分返回True转移遍历wordDict中每个单词若s[pos:poslen(word)] word且dp(pos len(word))为真则dp(pos)为真若所有单词都无法匹配返回False。仓库题解给出的 Python 核心递归写法如下使用cache做记忆化cache def dp(pos): if pos len(s): return True for word in wordDict: if s[pos:poslen(word)] word and dp(pos len(word)): return True return False return dp(0)其中cache等价于functools.lru_cache在实际提交时需要from functools import cachePython 3.9或from functools import lru_cache搭配lru_cache(None)使用。该版本的复杂度为 $O(n^2 \times m)$其中 $n$ 为字符串s的长度$m$ 为wordDict的长度递归深度最多 $n$每个状态内拼接比较的代价与 $m$ 相关。用图来感受递归展开的过程图的左边代表s右边代表字典dict灰色表示尚未处理的字符绿色表示匹配成功红色表示匹配失败。分步执行s leetcode、wordDict [leet, code]时递归会依次尝试在0位置匹配leet成功随后在4位置匹配code成功并触底返回True而对不可拆分的字符串递归会在某个位置穷尽所有单词后返回False并向上回溯。原题解还将这道题比喻为「往一个老式手电筒中装电池」每一节电池单词必须恰好塞进对应的槽位字符串前缀全部塞满且严丝合缝才算成功——如果某一节电池塞错了槽位后面的电池就装不进去需要换一种装法重新尝试这正是回溯与记忆化的形象化理解。思路三枚举切分长度 哈希集合复杂度与字典大小解耦思路二虽然正确但复杂度与m字典大小直接挂钩。进一步优化的关键点在于在dp函数内部直接枚举匹配的长度k而不是遍历字典。做法是固定当前位置pos枚举切分长度k即下一个单词占用的字符数截取s[pos:posk]只要这个子串存在于wordDict中就继续递归dp(pos k)不存在就换一个k继续尝试。而「判断s[pos:posk]是否在wordDict中」这一步可以通过把wordDict放入哈希集合set将查询优化到 $O(1)$代价是多占 $O(m)$ 的空间。class Solution: def wordBreak(self, s: str, wordDict: List[str]) - bool: wordDict set(wordDict) cache def dp(pos): if pos len(s): return True cur for nxt in range(pos, len(s)): cur s[nxt] if cur in wordDict and dp(nxt 1): return True return False return dp(0)这里cur逐字符累加等价于依次尝试s[pos:pos1]、s[pos:pos2]……所有可能的切分长度命中字典即向下递归。经过这一优化时间复杂度降为 $O(n^2)$与字典大小m无关。三语言完整实现仓库题解提供了 Python3、JavaScript、C 三种语言的实现其中 JS 与 CPP 版本采用自底向上的迭代式 DPdp[i]表示s的前i个字符是否可拆分与思路三的记忆化递归在本质上完全等价可以对照阅读。Python3记忆化递归 哈希集合class Solution: def wordBreak(self, s: str, wordDict: List[str]) - bool: wordDict set(wordDict) cache def dp(pos): if pos len(s): return True cur for nxt in range(pos, len(s)): cur s[nxt] if cur in wordDict and dp(nxt 1): return True return False return dp(0)JavaScript自底向上 DP/** * param {string} s * param {string[]} wordDict * return {boolean} */ var wordBreak function (s, wordDict) { const dp Array(s.length 1); dp[0] true; for (let i 0; i s.length 1; i) { for (let word of wordDict) { if (word.length i dp[i - word.length]) { if (s.substring(i - word.length, i) word) { dp[i] true; } } } } return dp[s.length] || false; };dp[i]记录前i个字符能否被拆分。枚举所有字典单词word若s[i - word.length : i]恰好等于word且前缀dp[i - word.length]可拆分则dp[i]置为true。最终返回dp[s.length]。C自底向上 DPclass Solution { public: bool wordBreak(string s, vectorstring dict) { unordered_setstring st(begin(dict), end(dict)); int N s.size(); vectorbool dp(N 1); dp[0] true; for (int i 1; i N; i) { for (int j 0; j i !dp[i]; j) { dp[i] dp[j] st.count(s.substr(j, i - j)); } } return dp[N]; } };dp[0] true表示空前缀可拆分对每个i枚举切分点j即上一个单词的结束位置当dp[j]为真且s[j:i]出现在哈希集合st中时dp[i]为真。注意内层循环条件!dp[i]一旦dp[i]已被置真即可提前终止该轮的枚举。复杂度分析令 $n$ 为字符串长度$m$ 为字典长度暴力匹配 / 未优化的记忆化递归时间复杂度 $O(n^2 \times m)$空间复杂度 $O(n m)$递归栈深度 $O(n)$字典占用 $O(m)$枚举切分长度 哈希集合优化后时间复杂度 $O(n^2)$——每个位置最多枚举 $O(n)$ 种切分长度每种切分借助哈希集合以 $O(1)$ 完成存在性判定且与字典大小m无关空间复杂度 $O(m)$哈希集合外加递归调用栈/记忆化数组的 $O(n)$。- 时间复杂度O(n ^ 2) - 空间复杂度O(m)仓库延伸进阶题与同类练习掌握 139 后可以在仓库中继续延伸输出全部拆分方案140. 单词拆分 II 是 139 的进阶版要求返回所有可能的句子。仓库题解先用暴力回溯求解再通过「将回溯结果以返回值传递给父级、以笛卡尔积构造答案」的方式引入记忆化把复杂度从 $O(2^N)$ 优化到 $O(N^2)$并给出一个长度为 151 的极限用例超长a串 十个由a组成的字典单词说明暴力回溯为何超时——这段分析对理解「记忆化递归与 DP 思想一模一样」非常直观DP 讲义推荐练习thinkings/dynamic-programming.md#L914-L925 建议对 91.decode-ways、198.house-robber、322.coin-change、416.partition-equal-subset-sum、518.coin-change-2 等题分别用记忆化递归与动态规划实现并尽可能用滚动数组优化空间——139 正是这套方法论的最佳入门样本题解索引本题收录于仓库 README 的题解目录0139. 单词拆分并按难度归入 collections/medium.md 的 Medium 集合。总结LeetCode 139「单词拆分」是字符串类动态规划的代表题解题链条环环相扣暴力匹配可行但昂贵重复子问题导致指数级回溯抓住「匹配成功后子问题规模缩小、性质不变」的观察用记忆化递归消除重复计算进一步把「遍历字典」改为「枚举切分长度 哈希集合 O(1) 判定」使时间复杂度从 $O(n^2 \times m)$ 优化到 $O(n^2)$与字典大小解耦记忆化递归与自底向上 DP 完全等价JS / C 版本即为迭代式写法可对照学习。掌握本题的「子问题分解 状态定义 转移枚举」三步法即可平滑迁移到单词拆分 II、解码方法、打家劫舍等同一套路下的系列题目。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考