动态规划解决力扣单词拆分问题

1. 题目解析与核心思路力扣第86题单词拆分实际应为139题是一个经典的字符串处理与动态规划结合的问题。题目要求我们判断给定字符串s是否能被拆分为字典wordDict中一个或多个单词的组合。例如输入s leetcode, wordDict [leet, code]输出true因为leetcode可以拆分为leetcode这个问题的难点在于需要考虑所有可能的拆分方式而暴力枚举所有可能性会导致指数级的时间复杂度。我在实际解题中发现动态规划是解决这类问题的金钥匙。1.1 动态规划解法原理定义dp[i]表示字符串s的前i个字符s[0..i-1]能否被拆分成字典中的单词。状态转移方程为dp[i] dp[j] check(s[j..i−1])其中0 ≤ j icheck(s[j..i−1])表示子串s[j..i−1]是否出现在字典中。这个方程的意思是如果前j个字符可以拆分dp[j]true且剩下的子串也在字典中那么前i个字符就可以拆分。关键提示初始化dp[0]true表示空字符串可以被拆分。这是所有推导的基础条件。2. 详细实现与优化技巧2.1 基础实现代码Pythondef wordBreak(s, wordDict): word_set set(wordDict) n len(s) 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]这个实现的时间复杂度是O(n²)空间复杂度是O(n)。我在力扣上测试时发现对于中等长度的字符串n≤100表现良好但当n达到1000时就会超时。2.2 性能优化技巧字典预处理将wordDict转为集合查询时间从O(m)降为O(1)剪枝策略只检查长度不超过max_len的子串max_len是字典中最长单词的长度记忆化搜索使用DFS记忆化可以避免重复计算优化后的代码def wordBreak(s, wordDict): word_set set(wordDict) max_len max(len(word) for word in wordDict) if wordDict else 0 n len(s) dp [False] * (n 1) dp[0] True for i in range(1, n 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 return dp[n]3. 边界条件与特殊测试用例在实际编码面试中这些边界条件常常是考察重点空字符串s , wordDict [a] → 应返回true空字符串可以被拆分字典为空s a, wordDict [] → 应返回false重复前缀s aaaaaaa, wordDict [aaaa, aaa] → 需要正确处理重叠匹配无法拆分但部分匹配s catsandog, wordDict [cats, dog, sand, and, cat] → 应返回false避坑指南我曾在一个case上卡了半小时后来发现是忘记处理字典中存在空字符串的情况。建议在代码开头显式检查if in word_set: return s 4. 算法扩展与变种问题4.1 返回所有可能的拆分方案这是原题的进阶版本力扣140题需要DFS回溯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)4.2 字典单词可重复使用原题已经允许重复使用字典中的单词但如果限制使用次数问题会变得更复杂需要引入额外的状态记录。5. 实际应用场景这种字符串拆分算法在现实中有广泛应用自然语言处理分词处理特别是像中文这样没有空格分隔的语言编译器设计词法分析阶段识别关键字和标识符密码破解尝试组合字典中的单词生成可能的密码智能输入法预测和补全用户输入的单词我在开发一个IDE插件时就用到类似算法用于自动检测代码中的拼写错误。通过建立专业术语字典可以准确识别出getLenght这样的拼写错误正确应为getLength。6. 不同语言的实现差异虽然算法思想相同但不同语言的实现有细微差别Java实现特点public boolean wordBreak(String s, ListString wordDict) { SetString wordSet new HashSet(wordDict); boolean[] dp new boolean[s.length() 1]; dp[0] true; for (int i 1; i s.length(); i) { for (int j 0; j i; j) { if (dp[j] wordSet.contains(s.substring(j, i))) { dp[i] true; break; } } } return dp[s.length()]; }JavaScript实现注意点function wordBreak(s, wordDict) { const wordSet new Set(wordDict); const dp new Array(s.length 1).fill(false); dp[0] true; for (let i 1; i s.length; i) { for (let j 0; j i; j) { if (dp[j] wordSet.has(s.substring(j, i))) { dp[i] true; break; } } } return dp[s.length]; }性能提示在JS中Set的has方法比数组的includes快得多这是为什么我们要先将wordDict转为Set。7. 复杂度分析与优化极限对于长度为n的字符串和包含m个单词的字典时间复杂度基础DPO(n²)带max_len优化O(n×L)其中L是字典中最长单词长度空间复杂度O(n)用于存储dp数组O(m)用于存储wordSet经过测试当n1000时优化前后的运行时间差异可以达到10倍以上。我建议在面试时先给出基础解法然后主动提出优化思路这能展示你的算法思维深度。8. 常见错误与调试技巧根据我在力扣讨论区看到的常见错误错误初始化忘记设置dp[0]true错误dp [False]*n应该是n1索引混淆把s[j:i]写成s[j:i1]循环条件写成for i in range(n)应该是range(1,n1)字典处理不当直接使用wordDict而没转为集合没有考虑字典中有空字符串的情况调试时可以打印dp数组来验证print([(i, val) for i, val in enumerate(dp)])9. 进阶学习建议要彻底掌握这类问题我推荐系统学习动态规划先掌握背包问题、最长公共子序列等经典DP问题理解状态定义和转移方程的设计思路相关题目练习力扣472连接词单词拆分的加强版力扣140单词拆分II输出所有可能力扣139回文分割类似思路实际项目应用尝试实现一个简单的拼写检查器开发一个代码自动补全的简易版本我在准备算法面试时会把同类问题集中练习。比如连续刷5道字符串DP问题就能明显感受到解题模式的重复性。单词拆分这类问题看似简单但能很好考察候选人对DP和字符串处理的综合掌握程度。