1. 先从题目本身聊起输入、输出与约束条件刷过一段 LeetCode 的人基本都会在动态规划专题里撞见这道leetcode139 单词拆分。题目本身并不长给你一个字符串s和一个单词字典wordDict请判断s能不能被拆分成一个或多个字典中出现的单词并且字典中的单词可以重复使用。比如s leetcodewordDict [leet, code]答案是true因为s可以拆成leetcode再比如s applepenapplewordDict [apple, pen]同样返回true因为apple出现了两次字典里的词本来就是可以复用的。这道题在面试里出现频率相当高尤其是大厂笔试和算法电面。它表面上是字符串处理内核却是非常典型的动态规划状态设计题同时还会牵扯到递归、记忆化搜索、哈希表优化甚至前缀树这些知识点。适合的读者也很明确准备面试的工程师、刚开始刷动态规划的新手以及想把这题迁移到其他拆分/拼接类问题的同学。把它吃透后面再遇到“拼接字符串”“凑单词”“能否组成目标串”这类问题你会觉得思路都是通的。1.1 题目到底在问什么很多人在第一眼看到这题时会下意识把它当成简单的包含关系判断。比如判断s是否包含wordDict里的某个单词或者s能否由某些单词的子串拼接出来。但题目真正要求的是对整个字符串做一次完整分割分割后的每一段都必须完整出现在词典里。注意措辞“拆分”不是“匹配到就算数”从开头到结尾必须被覆盖干净。举个例子你就明白了。s catsandogwordDict [cats, dog, sand, and, cat]。这里cat、cats、sand、and、dog都在字典里s也确实包含这些词但不管怎么切总有一块接不上你可以切catsandog但og不在字典里也可以切catsandog结果一样卡在og上直接切catsdog中间的andog显然没法切。所以最终答案是false。这个例子特别适合拿来检验你写的算法是真的在“从头到尾拆串”还是仅仅在“找包含关系”。题目还有个很容易忽略的细节wordDict是一个列表不是去重后的集合但实际使用中应该先转成哈希集合因为字典中可能包含重复单词。重复不会影响结果却会拖慢查询速度。另外字典里的单词可以被无限次使用这意味着这不是一个“每个单词只能用一次”的匹配问题而更像一个完全背包中的“物品可重复取”模型。1.2 两个最容易忽略的细节第一个细节是空字符串。LeetCode 原题一般给s.length 1但如果你要自己写测试用例或者面试官追问边界情况应该想一想s 应该返回什么。按照动态规划里dp[0] true的定义空串可以视为已经拆分完成不需要任何单词组合所以答案是true。这个约定不是拍脑袋定的它是状态转移的基石后面你会看到所有递推都从dp[0]出发。第二个细节是子串长度的控制。用dp[i]表示前i个字符是否可拆分时状态转移要枚举分界点j然后判断s[j:i]是否在字典中。这里的j必须从0遍历到i-1而不是只挑几个看起来像单词边界的位置。因为字典里的单词长度不固定你无法预判哪个位置能切开。即使你提前知道字典里最长的单词长度是maxLen也只敢在i - maxLen到i这个范围内枚举否则就可能漏掉一种拆分方式。2. 暴力回溯为什么跑不动看到“拆分成单词”这类描述很多人第一反应是递归。从下标0出发每次尝试匹配一段子串匹配成功就从下一位置继续递归直到指针走到字符串末尾。这套思路本身没毛病但它会踩中一个非常经典的性能陷阱重叠子问题。2.1 第一直觉的递归拆法来写个伪代码感受一下。定义一个递归函数dfs(start)表示当前要拆s[start:]这一段。函数里从end start 1开始一直试到s.length只要s[start:end]在字典里并且dfs(end)返回true那整个函数就返回true。如果所有尝试都失败返回false。用刚才的catsandog去跑你会发现它在一路尝试先试cat然后递归处理sandog在sandog里试sand然后处理og处理og时发现o、og都不在字典里于是返回false再回溯到sandog的下一刀试sandog本身发现不在字典里返回false再回溯到第一层试cats递归处理andog……这条路非常直观但效率极低。表面上的问题是枚举所有切割点本质上的问题是同一个子串会被反复计算。还是拿这个例子切catsand 后续和切catsand 后续两条不同路径最后都可能需要判断og或og附近剩余部分能不能拆。这些判断每次都重新递归一遍完全没有复用之前的结果。2.2 重叠子问题的定量分析我们可以把递归树画出来根节点是dfs(0)每一条边代表从某个位置切出一个字典单词。假设s很长而字典里恰好有大量短单词可以组合出它比如s aaaaab字典是[a, aa, aaa, aaaa]那么dfs(1)可能出现很多次你可以在位置0切一个a到dfs(1)也可以在位置0切一个aa到dfs(2)然后从dfs(2)内部再切一个a又回到dfs(1)严格说这里各路径到达dfs(1)的方式不同但数值上确实会多次重复调用同一个位置。最坏情况下每个位置都有多个单词可以匹配那么递归分支数是指数级的理论复杂度可以达到O(n * 2^n)左右。凡是碰到指数级递归第一反应就应该是“有没有重复计算能不能缓存”这也是动态规划题目的典型信号。如果面试时你先写了个回溯面试官多半会追问一句“时间复杂度多少”“能不能优化”这时候顺势引入记忆化搜索或动态规划反而能展现出你分析问题的能力。3. 动态规划才是这题的常规解暴力递归慢是因为不知道“哪些子问题已经算过了”。动态规划的思路很简单把“前i个字符能否被完整拆分”这个问题的答案按顺序从小往大算存进数组里后面直接查表。3.1 状态定义与转移方程定义dp[i]为布尔值表示字符串s的前i个字符即s[0:i]能否被拆分成字典中的单词。初始化dp[0] true因为空串天然满足“拆分完成”。接下来枚举 i 从 1 到 n每个 i 都在内部枚举分界点 j 从 0 到 i-1。转移条件有两个缺一不可dp[j]必须为true说明s[0:j]已经能拆干净s[j:i]必须是一个完整出现在字典里的单词。两个条件同时成立就可以把dp[i]置为true然后立即跳出内层循环因为只需要知道“能否拆分”不需要统计有多少种拆分方式。这个状态定义很像“跳台阶”问题dp[i]能否为真取决于是否存在一个合法的“落脚点”j从j到i恰好是一个词典单词。说白了我们在检查字符串是否能被若干词典单词头尾相接铺满。3.2 完整代码与复杂度直接给出一个常见、好读的 Python 实现def wordBreak(s: str, wordDict: list[str]) - bool: n len(s) word_set set(wordDict) dp [False] * (n 1) dp[0] True for i in range(1, n 1): for j in range(i): if dp[j] and s[j:i] in word_set: dp[i] True break return dp[n]再给一个 Java 版本方便对比class Solution { public boolean wordBreak(String s, ListString wordDict) { int n s.length(); SetString wordSet new HashSet(wordDict); 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] wordSet.contains(s.substring(j, i))) { dp[i] true; break; } } } return dp[n]; } }这里我把wordDict转成了哈希集合这是非常重要的一步。如果不转每次s[j:i] in wordDict都是对列表做线性扫描整体复杂度会再乘上一个m字典长度在字典特别大的时候会非常难受。转换成哈希集合后单次查询是O(1)。至于复杂度外层循环跑n次内层循环平均跑i次所以总共会产生O(n^2)对(j, i)候选每一对候选都要从字符串中截取一段s[j:i]截取本身需要O(i-j)的时间所以最坏情况是O(n^3)。不过在实际刷题时很多人习惯把它说成O(n^2)因为当单词长度不大、且命中后立即break实际跑起来很快。如果你想要一份更严谨的表达可以说时间复杂度取决于字符串长度和词典中最大单词长度理论上界是O(n^3)但通过长度剪枝可以显著压低。3.3 一个小优化限制单词长度既然内层循环每次都要从j 0扫到j i-1那在字符串很长、字典单词普遍很短时这其实做了很多无用功。一个非常实用的优化是先统计wordDict里最长单词的长度max_len内层循环不再从0开始而是从i - max_len开始。因为s[j:i]的长度如果已经超过了字典里最长单词的长度它肯定不可能出现在字典里没必要检查。def wordBreak(s: str, wordDict: list[str]) - bool: n len(s) word_set set(wordDict) max_len max(len(w) for w in wordDict) dp [False] * (n 1) dp[0] True for i in range(1, n 1): start max(0, i - max_len) for j in range(start, i): if dp[j] and s[j:i] in word_set: dp[i] True break return dp[n]不要小看这个改动。当s长度是 1000而字典里最长的单词只有 10 个字符时内层循环从平均 500 次降到最多 10 次整体速度快了 50 倍。我在本地用长字符串压过长度剪枝版本几乎没有任何卡顿。面试时主动加这一步是很强的加分项因为它体现的不是“背题”而是真的理解瓶颈在哪。4. 从递归到记忆化三条代码路径的现场对比动态规划不是唯一能把指数级递归救回来的方法。另一种常见手段是记忆化搜索也就是在递归函数里加一个缓存。理解这两种写法的区别能让你在面试时不至于被追问“为什么不用 DFS”就卡壳。4.1 记忆化搜索的实现递归函数的定义可以改成dfs(i)表示s[i:]这一段能否被拆分。注意这和前面dp[i]的定义方向相反dp[i]看的是前缀dfs(i)看的是后缀。但本质上都在描述同一个子问题。代码如下def wordBreak(s: str, wordDict: list[str]) - bool: word_set set(wordDict) n len(s) memo [-1] * n # -1 表示未计算0 表示不可拆1 表示可拆 def dfs(i: int) - bool: if i n: return True if memo[i] ! -1: return memo[i] 1 for end in range(i 1, n 1): if s[i:end] in word_set and dfs(end): memo[i] 1 return True memo[i] 0 return False return dfs(0)这段逻辑和纯回溯一模一样唯一区别是每次算完memo[i]下次再碰到同样的i直接返回结果不再重复展开递归树。它和动态规划是等价的只是计算顺序不同动态规划是自底向上记忆化搜索是自顶向下。如果你对递推方向容易搞混可以先写记忆化版本它更贴近人的直觉。注意这里memo数组在用memo[i] 1和memo[i] 0时一定把“未计算”和“不可拆”区分开。如果只用True/False做缓存很容易把第一次算出的False当成“还没算”导致重复计算。4.2 三种解法的横向对比为了让你看得更清楚我把三种写法放在一起对比解法时间复杂度空间复杂度优点缺点纯回溯O(n * 2^n)O(n) 递归栈思路直观好写大量重复子问题严重超时记忆化搜索O(n^2) 到 O(n^3)O(n) 缓存 递归栈直观 复用结果有递归栈溢出风险一般 n 不超过 300 没事动态规划O(n^2) 到 O(n^3)O(n)无递归开销代码短状态转移方向需要想清楚刷题时我个人的习惯是先想状态定义再想转移方程然后直接写动态规划。但如果你在紧张的状态下一时半会想不出dp怎么写记忆化搜索是完全可接受的保底方案。面试官更看重的是你能不能给出“从暴力到优化”的演进过程而不是直接默写一个最优解。关于空间复杂度动态规划和记忆化搜索都要存长度为n1的状态所以都是O(n)。唯一的额外开销是记忆化搜索需要递归栈最坏情况下递归深度能达到n层虽然 LeetCode 这题的s长度一般不大但如果在极端评测环境里递归层数很深的题还是要优先选非递归的动态规划。5. 进阶四个高频变体与考点延伸5.1 输出所有拆分方案leetcode139只要求返回true/false但如果面试官让你“给出所有可能的拆分方案”那就是另一道经典题了。最简单的方式是先跑一遍动态规划拿到dp数组然后从后往前回溯拼接。我写过一个参考思路先用wordBreak的dp确定哪些分割点可行再写一个backtrack(start, path)从start开始尝试所有end只要dp[end]为真且s[start:end]在字典里就把这段加入路径递归处理end。当start到达字符串末尾时把path保存下来。这个方法能大幅剪枝因为只会在“前缀可拆分”的正确分割点上展开不会像纯回溯那样把整棵错误分支都遍历一遍。如果你在面试中能主动说出“先用 dp 做可行性剪枝再回溯收集方案”这比裸写一个 DFS 要高级得多。5.2 单词拆分与完全背包的统一视角这题换个角度看其实是个完全背包问题s是背包容量字典里的单词是物品单词可以无限次使用目标不是让价值最大而是判断能不能恰好填满。状态dp[i]表示容量i能否完全由物品拼出转移时枚举最后一个放入的物品单词这个思路和经典的“凑零钱”问题一脉相承。我之所以强调这个统一视角是因为面试时问题经常不会只考原题。比如改成“给定一个字符串和单词列表判断能否拆分成单词且拆分次数最少”“能否用这些单词拼接成目标串每个单词最多用一次”这些题的核心状态都是类似的dp[i]只是转移条件、使用次数限制稍有变化。把139吃透等于给这一类题都打了底。5.3 大词典场景下用 Trie 进一步提速当wordDict非常大或者单词长度参差不齐时哈希集合已经够用但如果要追求极致性能可以用前缀树Trie。具体做法是把字典中所有单词插入 Tries[j:i]是否在字典中等价于从 Trie 根节点开始沿着字符往下走能不能走到一个单词结束标记。换用 Trie 的好处是判断子串时不用每次在原字符串上截取而是一边走一边检查前缀一旦发现某个前缀在 Trie 中不存在就可以提前终止。这个优化在处理长串和长词典时尤其明显。代价是实现代码变长面试时间紧张时不建议主动引入除非面试官明确问“能不能优化到更快”。5.4 其他变体返回方案数还有一个常见变体是“返回拆分方案总数”比如s leetcode字典里有[leet, code, leetcode]方案数应该是 2一种是leet code一种是leetcode整体。这个题把布尔dp改成整数dpdp[i]表示前i个字符的拆分方案数转移时把所有满足条件的dp[j]累加即可。需要注意方案数可能非常大题目如果没说明取模要用 Python 的整数不用担心溢出但在 Java/C 里可能要考虑long或者取模。这已经属于139的延伸讨论了但是在面试中遇到变体题时非常有用。6. 面试与实战中的常见坑和排查思路6.1 五个高频 bugbug 1忘记初始化dp[0] true。这是最经典的失误。没有dp[0]所有转移都从空集出发结果大概率是false。面试时写完代码一定要用s a, wordDict [a]这种最小用例手动走一遍确认dp[1]能正确变成true。bug 2break位置写错。内层循环一旦找到一个合法分界点就应该立刻置dp[i] true并跳出。有些人会把break写在if dp[j]这个外层判断里导致没有检查s[j:i]是否在字典中就提前结束整个逻辑就废了。bug 3忘记把wordDict转成哈希集合。如果直接用列表做包含判断虽然结果没错但复杂度从O(n^3)直接飙升到O(n^3 * m)。在 LeetCode 上表现就是超时而且很难排查。写完代码第一件事看看你的查询对象是不是集合。bug 4下标和切片区间对不上。dp数组长度是n1dp[i]对应s的前i个字符所以s[j:i]的j、i都是下标端点而不是“第几个字符”。很多人在手动模拟s abcd时会把dp[2]误解成bc可拆分实际它对应的是ab。一定要在脑内把“前 i 个字符”这个定义钉死。bug 5忽视重复点击的边界。优化长度剪枝时start max(0, i - max_len)这个max(0, ...)非常关键。如果i本身小于max_leni - max_len会变成负数Python 切片负数不会立刻报错但会从尾部开始取结果完全错误。别问我怎么知道的这种坑一旦踩过就再也不会忘。6.2 性能排查与优化清单如果你写完动态规划还是超时别急着怀疑编译器按这个顺序排查第一wordDict是否已转哈希集合第二内层循环是否做了大量无效截取第三是否能用最大单词长度剪枝第四dp[i]是否提前break第五极端情况下考虑 Trie 替代哈希集合。我实测过一个案例s长度 200wordDict有 500 个单词不做任何优化时哈希集合版本大约几毫秒如果误用了列表直接卡到几秒甚至更久。别小看这些常量的差异LeetCode 的评测数据往往就是卡着极限来的。6.3 面试时推荐的讲述节奏面试中遇到这题不要上来就写代码。先和面试官确认三件事s可以为空吗wordDict里允许重复吗返回只需要布尔值还是需要方案确认完再讲思路。我建议的讲述顺序是第一说清楚状态dp[i]的定义第二写出转移方程“dp[i]为真当且仅当存在j使dp[j]为真且s[j:i]在字典中”第三解释为什么dp[0] true第四用一个小的例子手动推一遍最后再写代码。这样面试官能跟着你的思路走而不是看着你闷头写。写完代码后主动补一句“这里可以把字典转成哈希集合还可以用最大单词长度剪枝”基本就把这道题吃透了。就我个人刷题经验来说这题真正的价值不在于你背下了dp写法而在于你理解了“子串拼接覆盖”这类问题的共性先划分阶段、定义状态再想转移条件。把这套思维方式练熟后面再遇到其他拆分题你甚至不需要犹豫就能直接写出状态数组。如果时间充裕我建议你把这题的三种写法都本地跑一遍感受一下指数级回调和动态规划的差距这种体感比看一百篇题解都深刻。 动态规划详解：LeetCode 139 单词拆分题解与优化
1. 先从题目本身聊起输入、输出与约束条件刷过一段 LeetCode 的人基本都会在动态规划专题里撞见这道leetcode139 单词拆分。题目本身并不长给你一个字符串s和一个单词字典wordDict请判断s能不能被拆分成一个或多个字典中出现的单词并且字典中的单词可以重复使用。比如s leetcodewordDict [leet, code]答案是true因为s可以拆成leetcode再比如s applepenapplewordDict [apple, pen]同样返回true因为apple出现了两次字典里的词本来就是可以复用的。这道题在面试里出现频率相当高尤其是大厂笔试和算法电面。它表面上是字符串处理内核却是非常典型的动态规划状态设计题同时还会牵扯到递归、记忆化搜索、哈希表优化甚至前缀树这些知识点。适合的读者也很明确准备面试的工程师、刚开始刷动态规划的新手以及想把这题迁移到其他拆分/拼接类问题的同学。把它吃透后面再遇到“拼接字符串”“凑单词”“能否组成目标串”这类问题你会觉得思路都是通的。1.1 题目到底在问什么很多人在第一眼看到这题时会下意识把它当成简单的包含关系判断。比如判断s是否包含wordDict里的某个单词或者s能否由某些单词的子串拼接出来。但题目真正要求的是对整个字符串做一次完整分割分割后的每一段都必须完整出现在词典里。注意措辞“拆分”不是“匹配到就算数”从开头到结尾必须被覆盖干净。举个例子你就明白了。s catsandogwordDict [cats, dog, sand, and, cat]。这里cat、cats、sand、and、dog都在字典里s也确实包含这些词但不管怎么切总有一块接不上你可以切catsandog但og不在字典里也可以切catsandog结果一样卡在og上直接切catsdog中间的andog显然没法切。所以最终答案是false。这个例子特别适合拿来检验你写的算法是真的在“从头到尾拆串”还是仅仅在“找包含关系”。题目还有个很容易忽略的细节wordDict是一个列表不是去重后的集合但实际使用中应该先转成哈希集合因为字典中可能包含重复单词。重复不会影响结果却会拖慢查询速度。另外字典里的单词可以被无限次使用这意味着这不是一个“每个单词只能用一次”的匹配问题而更像一个完全背包中的“物品可重复取”模型。1.2 两个最容易忽略的细节第一个细节是空字符串。LeetCode 原题一般给s.length 1但如果你要自己写测试用例或者面试官追问边界情况应该想一想s 应该返回什么。按照动态规划里dp[0] true的定义空串可以视为已经拆分完成不需要任何单词组合所以答案是true。这个约定不是拍脑袋定的它是状态转移的基石后面你会看到所有递推都从dp[0]出发。第二个细节是子串长度的控制。用dp[i]表示前i个字符是否可拆分时状态转移要枚举分界点j然后判断s[j:i]是否在字典中。这里的j必须从0遍历到i-1而不是只挑几个看起来像单词边界的位置。因为字典里的单词长度不固定你无法预判哪个位置能切开。即使你提前知道字典里最长的单词长度是maxLen也只敢在i - maxLen到i这个范围内枚举否则就可能漏掉一种拆分方式。2. 暴力回溯为什么跑不动看到“拆分成单词”这类描述很多人第一反应是递归。从下标0出发每次尝试匹配一段子串匹配成功就从下一位置继续递归直到指针走到字符串末尾。这套思路本身没毛病但它会踩中一个非常经典的性能陷阱重叠子问题。2.1 第一直觉的递归拆法来写个伪代码感受一下。定义一个递归函数dfs(start)表示当前要拆s[start:]这一段。函数里从end start 1开始一直试到s.length只要s[start:end]在字典里并且dfs(end)返回true那整个函数就返回true。如果所有尝试都失败返回false。用刚才的catsandog去跑你会发现它在一路尝试先试cat然后递归处理sandog在sandog里试sand然后处理og处理og时发现o、og都不在字典里于是返回false再回溯到sandog的下一刀试sandog本身发现不在字典里返回false再回溯到第一层试cats递归处理andog……这条路非常直观但效率极低。表面上的问题是枚举所有切割点本质上的问题是同一个子串会被反复计算。还是拿这个例子切catsand 后续和切catsand 后续两条不同路径最后都可能需要判断og或og附近剩余部分能不能拆。这些判断每次都重新递归一遍完全没有复用之前的结果。2.2 重叠子问题的定量分析我们可以把递归树画出来根节点是dfs(0)每一条边代表从某个位置切出一个字典单词。假设s很长而字典里恰好有大量短单词可以组合出它比如s aaaaab字典是[a, aa, aaa, aaaa]那么dfs(1)可能出现很多次你可以在位置0切一个a到dfs(1)也可以在位置0切一个aa到dfs(2)然后从dfs(2)内部再切一个a又回到dfs(1)严格说这里各路径到达dfs(1)的方式不同但数值上确实会多次重复调用同一个位置。最坏情况下每个位置都有多个单词可以匹配那么递归分支数是指数级的理论复杂度可以达到O(n * 2^n)左右。凡是碰到指数级递归第一反应就应该是“有没有重复计算能不能缓存”这也是动态规划题目的典型信号。如果面试时你先写了个回溯面试官多半会追问一句“时间复杂度多少”“能不能优化”这时候顺势引入记忆化搜索或动态规划反而能展现出你分析问题的能力。3. 动态规划才是这题的常规解暴力递归慢是因为不知道“哪些子问题已经算过了”。动态规划的思路很简单把“前i个字符能否被完整拆分”这个问题的答案按顺序从小往大算存进数组里后面直接查表。3.1 状态定义与转移方程定义dp[i]为布尔值表示字符串s的前i个字符即s[0:i]能否被拆分成字典中的单词。初始化dp[0] true因为空串天然满足“拆分完成”。接下来枚举 i 从 1 到 n每个 i 都在内部枚举分界点 j 从 0 到 i-1。转移条件有两个缺一不可dp[j]必须为true说明s[0:j]已经能拆干净s[j:i]必须是一个完整出现在字典里的单词。两个条件同时成立就可以把dp[i]置为true然后立即跳出内层循环因为只需要知道“能否拆分”不需要统计有多少种拆分方式。这个状态定义很像“跳台阶”问题dp[i]能否为真取决于是否存在一个合法的“落脚点”j从j到i恰好是一个词典单词。说白了我们在检查字符串是否能被若干词典单词头尾相接铺满。3.2 完整代码与复杂度直接给出一个常见、好读的 Python 实现def wordBreak(s: str, wordDict: list[str]) - bool: n len(s) word_set set(wordDict) dp [False] * (n 1) dp[0] True for i in range(1, n 1): for j in range(i): if dp[j] and s[j:i] in word_set: dp[i] True break return dp[n]再给一个 Java 版本方便对比class Solution { public boolean wordBreak(String s, ListString wordDict) { int n s.length(); SetString wordSet new HashSet(wordDict); 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] wordSet.contains(s.substring(j, i))) { dp[i] true; break; } } } return dp[n]; } }这里我把wordDict转成了哈希集合这是非常重要的一步。如果不转每次s[j:i] in wordDict都是对列表做线性扫描整体复杂度会再乘上一个m字典长度在字典特别大的时候会非常难受。转换成哈希集合后单次查询是O(1)。至于复杂度外层循环跑n次内层循环平均跑i次所以总共会产生O(n^2)对(j, i)候选每一对候选都要从字符串中截取一段s[j:i]截取本身需要O(i-j)的时间所以最坏情况是O(n^3)。不过在实际刷题时很多人习惯把它说成O(n^2)因为当单词长度不大、且命中后立即break实际跑起来很快。如果你想要一份更严谨的表达可以说时间复杂度取决于字符串长度和词典中最大单词长度理论上界是O(n^3)但通过长度剪枝可以显著压低。3.3 一个小优化限制单词长度既然内层循环每次都要从j 0扫到j i-1那在字符串很长、字典单词普遍很短时这其实做了很多无用功。一个非常实用的优化是先统计wordDict里最长单词的长度max_len内层循环不再从0开始而是从i - max_len开始。因为s[j:i]的长度如果已经超过了字典里最长单词的长度它肯定不可能出现在字典里没必要检查。def wordBreak(s: str, wordDict: list[str]) - bool: n len(s) word_set set(wordDict) max_len max(len(w) for w in wordDict) dp [False] * (n 1) dp[0] True for i in range(1, n 1): start max(0, i - max_len) for j in range(start, i): if dp[j] and s[j:i] in word_set: dp[i] True break return dp[n]不要小看这个改动。当s长度是 1000而字典里最长的单词只有 10 个字符时内层循环从平均 500 次降到最多 10 次整体速度快了 50 倍。我在本地用长字符串压过长度剪枝版本几乎没有任何卡顿。面试时主动加这一步是很强的加分项因为它体现的不是“背题”而是真的理解瓶颈在哪。4. 从递归到记忆化三条代码路径的现场对比动态规划不是唯一能把指数级递归救回来的方法。另一种常见手段是记忆化搜索也就是在递归函数里加一个缓存。理解这两种写法的区别能让你在面试时不至于被追问“为什么不用 DFS”就卡壳。4.1 记忆化搜索的实现递归函数的定义可以改成dfs(i)表示s[i:]这一段能否被拆分。注意这和前面dp[i]的定义方向相反dp[i]看的是前缀dfs(i)看的是后缀。但本质上都在描述同一个子问题。代码如下def wordBreak(s: str, wordDict: list[str]) - bool: word_set set(wordDict) n len(s) memo [-1] * n # -1 表示未计算0 表示不可拆1 表示可拆 def dfs(i: int) - bool: if i n: return True if memo[i] ! -1: return memo[i] 1 for end in range(i 1, n 1): if s[i:end] in word_set and dfs(end): memo[i] 1 return True memo[i] 0 return False return dfs(0)这段逻辑和纯回溯一模一样唯一区别是每次算完memo[i]下次再碰到同样的i直接返回结果不再重复展开递归树。它和动态规划是等价的只是计算顺序不同动态规划是自底向上记忆化搜索是自顶向下。如果你对递推方向容易搞混可以先写记忆化版本它更贴近人的直觉。注意这里memo数组在用memo[i] 1和memo[i] 0时一定把“未计算”和“不可拆”区分开。如果只用True/False做缓存很容易把第一次算出的False当成“还没算”导致重复计算。4.2 三种解法的横向对比为了让你看得更清楚我把三种写法放在一起对比解法时间复杂度空间复杂度优点缺点纯回溯O(n * 2^n)O(n) 递归栈思路直观好写大量重复子问题严重超时记忆化搜索O(n^2) 到 O(n^3)O(n) 缓存 递归栈直观 复用结果有递归栈溢出风险一般 n 不超过 300 没事动态规划O(n^2) 到 O(n^3)O(n)无递归开销代码短状态转移方向需要想清楚刷题时我个人的习惯是先想状态定义再想转移方程然后直接写动态规划。但如果你在紧张的状态下一时半会想不出dp怎么写记忆化搜索是完全可接受的保底方案。面试官更看重的是你能不能给出“从暴力到优化”的演进过程而不是直接默写一个最优解。关于空间复杂度动态规划和记忆化搜索都要存长度为n1的状态所以都是O(n)。唯一的额外开销是记忆化搜索需要递归栈最坏情况下递归深度能达到n层虽然 LeetCode 这题的s长度一般不大但如果在极端评测环境里递归层数很深的题还是要优先选非递归的动态规划。5. 进阶四个高频变体与考点延伸5.1 输出所有拆分方案leetcode139只要求返回true/false但如果面试官让你“给出所有可能的拆分方案”那就是另一道经典题了。最简单的方式是先跑一遍动态规划拿到dp数组然后从后往前回溯拼接。我写过一个参考思路先用wordBreak的dp确定哪些分割点可行再写一个backtrack(start, path)从start开始尝试所有end只要dp[end]为真且s[start:end]在字典里就把这段加入路径递归处理end。当start到达字符串末尾时把path保存下来。这个方法能大幅剪枝因为只会在“前缀可拆分”的正确分割点上展开不会像纯回溯那样把整棵错误分支都遍历一遍。如果你在面试中能主动说出“先用 dp 做可行性剪枝再回溯收集方案”这比裸写一个 DFS 要高级得多。5.2 单词拆分与完全背包的统一视角这题换个角度看其实是个完全背包问题s是背包容量字典里的单词是物品单词可以无限次使用目标不是让价值最大而是判断能不能恰好填满。状态dp[i]表示容量i能否完全由物品拼出转移时枚举最后一个放入的物品单词这个思路和经典的“凑零钱”问题一脉相承。我之所以强调这个统一视角是因为面试时问题经常不会只考原题。比如改成“给定一个字符串和单词列表判断能否拆分成单词且拆分次数最少”“能否用这些单词拼接成目标串每个单词最多用一次”这些题的核心状态都是类似的dp[i]只是转移条件、使用次数限制稍有变化。把139吃透等于给这一类题都打了底。5.3 大词典场景下用 Trie 进一步提速当wordDict非常大或者单词长度参差不齐时哈希集合已经够用但如果要追求极致性能可以用前缀树Trie。具体做法是把字典中所有单词插入 Tries[j:i]是否在字典中等价于从 Trie 根节点开始沿着字符往下走能不能走到一个单词结束标记。换用 Trie 的好处是判断子串时不用每次在原字符串上截取而是一边走一边检查前缀一旦发现某个前缀在 Trie 中不存在就可以提前终止。这个优化在处理长串和长词典时尤其明显。代价是实现代码变长面试时间紧张时不建议主动引入除非面试官明确问“能不能优化到更快”。5.4 其他变体返回方案数还有一个常见变体是“返回拆分方案总数”比如s leetcode字典里有[leet, code, leetcode]方案数应该是 2一种是leet code一种是leetcode整体。这个题把布尔dp改成整数dpdp[i]表示前i个字符的拆分方案数转移时把所有满足条件的dp[j]累加即可。需要注意方案数可能非常大题目如果没说明取模要用 Python 的整数不用担心溢出但在 Java/C 里可能要考虑long或者取模。这已经属于139的延伸讨论了但是在面试中遇到变体题时非常有用。6. 面试与实战中的常见坑和排查思路6.1 五个高频 bugbug 1忘记初始化dp[0] true。这是最经典的失误。没有dp[0]所有转移都从空集出发结果大概率是false。面试时写完代码一定要用s a, wordDict [a]这种最小用例手动走一遍确认dp[1]能正确变成true。bug 2break位置写错。内层循环一旦找到一个合法分界点就应该立刻置dp[i] true并跳出。有些人会把break写在if dp[j]这个外层判断里导致没有检查s[j:i]是否在字典中就提前结束整个逻辑就废了。bug 3忘记把wordDict转成哈希集合。如果直接用列表做包含判断虽然结果没错但复杂度从O(n^3)直接飙升到O(n^3 * m)。在 LeetCode 上表现就是超时而且很难排查。写完代码第一件事看看你的查询对象是不是集合。bug 4下标和切片区间对不上。dp数组长度是n1dp[i]对应s的前i个字符所以s[j:i]的j、i都是下标端点而不是“第几个字符”。很多人在手动模拟s abcd时会把dp[2]误解成bc可拆分实际它对应的是ab。一定要在脑内把“前 i 个字符”这个定义钉死。bug 5忽视重复点击的边界。优化长度剪枝时start max(0, i - max_len)这个max(0, ...)非常关键。如果i本身小于max_leni - max_len会变成负数Python 切片负数不会立刻报错但会从尾部开始取结果完全错误。别问我怎么知道的这种坑一旦踩过就再也不会忘。6.2 性能排查与优化清单如果你写完动态规划还是超时别急着怀疑编译器按这个顺序排查第一wordDict是否已转哈希集合第二内层循环是否做了大量无效截取第三是否能用最大单词长度剪枝第四dp[i]是否提前break第五极端情况下考虑 Trie 替代哈希集合。我实测过一个案例s长度 200wordDict有 500 个单词不做任何优化时哈希集合版本大约几毫秒如果误用了列表直接卡到几秒甚至更久。别小看这些常量的差异LeetCode 的评测数据往往就是卡着极限来的。6.3 面试时推荐的讲述节奏面试中遇到这题不要上来就写代码。先和面试官确认三件事s可以为空吗wordDict里允许重复吗返回只需要布尔值还是需要方案确认完再讲思路。我建议的讲述顺序是第一说清楚状态dp[i]的定义第二写出转移方程“dp[i]为真当且仅当存在j使dp[j]为真且s[j:i]在字典中”第三解释为什么dp[0] true第四用一个小的例子手动推一遍最后再写代码。这样面试官能跟着你的思路走而不是看着你闷头写。写完代码后主动补一句“这里可以把字典转成哈希集合还可以用最大单词长度剪枝”基本就把这道题吃透了。就我个人刷题经验来说这题真正的价值不在于你背下了dp写法而在于你理解了“子串拼接覆盖”这类问题的共性先划分阶段、定义状态再想转移条件。把这套思维方式练熟后面再遇到其他拆分题你甚至不需要犹豫就能直接写出状态数组。如果时间充裕我建议你把这题的三种写法都本地跑一遍感受一下指数级回调和动态规划的差距这种体感比看一百篇题解都深刻。