1. 问题背景与核心需求今天咱们来啃一道LeetCode高频面试题——第139题单词拆分。这道题在Google、Meta、Amazon等大厂面试中出现的频率相当高属于必须掌握的动态规划经典题型。题目描述很简单给定一个非空字符串s和一个包含非空单词列表的字典wordDict判断s是否能被分割成一个或多个字典中单词的空格分隔序列。举个实际例子输入s leetcode, wordDict [leet, code]输出true解释leetcode可以拆分为leet code这个问题看似简单但隐藏着几个关键陷阱字典中的单词可以重复使用不需要使用字典中所有的单词拆分时必须完全匹配不能有剩余字符2. 暴力递归解法与缺陷分析2.1 最直观的递归思路很多同学的第一反应是用递归尝试所有可能的拆分方式def wordBreak(s, wordDict): def dfs(s): if not s: return True for word in wordDict: if s.startswith(word): if dfs(s[len(word):]): return True return False return dfs(s)这个解法在逻辑上是正确的但存在严重的性能问题。考虑这个测试用例 s aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab wordDict [a,aa,aaa,aaaa,aaaaa,aaaaaa,aaaaaaa,aaaaaaaa,aaaaaaaaa,aaaaaaaaaa]这种情况下递归会产生指数级的时间复杂度O(2^n)因为每个字符位置都有多种分割可能导致大量重复计算。2.2 重复子问题分析仔细观察会发现在递归过程中我们会反复处理相同的子字符串。比如在判断leetcode时先尝试leetcode也可能尝试leetcode失败后继续尝试其他组合这种重复计算是性能瓶颈的关键。这正是动态规划典型的适用场景——具有重叠子问题和最优子结构性质。3. 动态规划解法详解3.1 DP数组定义与状态转移我们定义dp[i]表示字符串s的前i个字符s[0..i-1]能否被字典中的单词拆分。状态转移方程为dp[i] any(dp[j] and s[j:i] in wordDict for j in range(i))解释遍历所有可能的分割点j0 ≤ j i如果前j个字符可以拆分dp[j]True且子串s[j..i-1]在字典中则前i个字符可以拆分3.2 完整DP实现def wordBreak(s, wordDict): word_set set(wordDict) dp [False] * (len(s) 1) dp[0] True # 空字符串可以被拆分 for i in range(1, len(s)1): for j in range(i): if dp[j] and s[j:i] in word_set: dp[i] True break return dp[len(s)]这个解法的时间复杂度是O(n^2)空间复杂度O(n)其中n是字符串长度。相比暴力解法有了质的飞跃。3.3 关键优化点将wordDict转为集合in操作的时间复杂度从O(m)降到O(1)m是字典大小内层循环找到有效分割立即break避免不必要的计算dp数组大小设为len(s)1方便处理空字符串情况4. 剪枝优化与边界处理4.1 基于最大单词长度的剪枝观察到一个重要性质如果字典中最长单词长度为max_len那么任何超过max_len的分割都不可能成功。因此可以优化内层循环max_len max(len(word) for word in wordDict) if wordDict else 0 for i in range(1, len(s)1): start max(0, i - max_len) if max_len else 0 for j in range(start, i): if dp[j] and s[j:i] in word_set: dp[i] True break这个优化将内层循环次数从i次减少到min(i, max_len)次对于长字符串效果显著。4.2 边界条件处理需要特别注意的特殊情况空字符串按照题意应该返回True字典为空除非s也是空字符串否则False字典中包含空字符串虽然题目说单词非空但实际处理时可以提前过滤5. 实际面试中的变种问题面试官可能会基于这道题提出各种变种常见的有5.1 返回所有可能的拆分方案这时需要修改DP为记忆化搜索记录所有可能的前驱状态def wordBreak(s, wordDict): word_set set(wordDict) memo {} def dfs(s): if s in memo: return memo[s] if not s: return [] res [] for word in word_set: if s.startswith(word): for substr in dfs(s[len(word):]): res.append(word ( substr if substr else )) memo[s] res return res return dfs(s)5.2 字典中存在特殊字符如果字典中包含正则表达式特殊字符如., *等需要先对字典进行转义处理或者改用re.fullmatch进行匹配。5.3 超大字典优化当字典非常大时如整个英语词典可以考虑使用Trie树加速前缀匹配对字典按单词长度分组布隆过滤器快速排除不可能匹配6. 复杂度分析与算法选择6.1 各解法对比方法时间复杂度空间复杂度适用场景暴力递归O(2^n)O(n)仅用于理解问题记忆化递归O(n^2)O(n)需要所有解时动态规划O(n^2)O(n)标准解法DP剪枝O(n*max_len)O(n)字典单词长度有限时6.2 为什么DP比DFSBFS更优有些同学可能会想到用BFS或DFS记忆化为什么DP是最佳选择BFS需要维护队列和访问记录空间复杂度可能更高DFS记忆化本质上和DP思路相同但DP的迭代形式通常更高效DP可以自然地记录中间结果方便后续扩展如求最小分割次数7. 实战中的常见错误与调试技巧7.1 易错点清单忘记处理空字符串情况dp数组大小设错应该是len(s)1不是len(s)字符串切片边界错误Python中s[j:i]是j到i-1没有将wordDict转为集合导致超时在DP中过早break导致漏解当需要所有解时7.2 调试方法打印dp数组观察每个位置是如何被更新的print(fdp[{i}]{dp[i]} via s[{j}:{i}]{s[j:i]})小样例测试先用简单案例验证如sa, wordDict[a]极端测试超长字符串、超大字典、特殊字符等情况8. 扩展思考与相关题目理解这道题后可以尝试解决这些变种单词拆分II返回所有可能拆分连接词找出所有可由字典中其他单词组成的单词139的follow-up求最少需要多少次拆分判断是否可以用字典中的单词拼接出目标字符串考虑顺序这类字符串分解问题在真实场景中也很常见比如自然语言处理中的分词编译器中的词法分析数据解析时的字段分割掌握动态规划解决字符串问题的套路可以举一反三应对各种变种题目。核心思路都是定义dp[i]表示前i个字符的性质然后通过状态转移方程逐步构建解。