1. 题目解析与核心思路力扣第139题单词拆分是一个经典的动态规划问题题目要求我们判断给定字符串s是否能被拆分成字典wordDict中的单词序列。这个问题的实际应用场景非常广泛比如在自然语言处理中的分词、编译器设计中的词法分析等场景都会遇到类似需求。1.1 问题描述重述给定一个非空字符串s和一个包含非空单词列表的字典wordDict确定s是否可以被分割为一个或多个字典单词的空格分隔序列。注意字典中的单词可以重复使用不要求使用字典中的所有单词示例 输入s leetcode, wordDict [leet, code] 输出true 解释leetcode可以被拆分为leet code1.2 暴力解法分析最直观的解法是使用回溯法尝试所有可能的分割方式从字符串开头开始尝试所有可能的单词匹配如果找到匹配的单词递归处理剩余部分如果所有可能性都尝试过仍无法完全匹配则返回false这种解法在最坏情况下时间复杂度为O(2^n)因为每个字符位置都有分割和不分割两种选择。对于较长的字符串这种解法显然不够高效。2. 动态规划解法详解动态规划是解决这个问题的更优方案可以将时间复杂度降低到O(n^2)。2.1 状态定义我们定义dp[i]表示字符串s的前i个字符即s[0..i-1]能否被字典中的单词拆分。最终我们需要求解的是dp[n]其中n是字符串s的长度。2.2 状态转移方程对于每个位置i我们需要检查所有可能的分割点j0 ≤ j i如果dp[j]为true即前j个字符可以被拆分且子串s[j..i-1]存在于字典中那么dp[i]就为true。状态转移方程可以表示为 dp[i] dp[j] (s[j..i-1] in wordDict) for any j i2.3 初始化dp[0] true表示空字符串可以被拆分这是递归的基准情况2.4 算法实现步骤将wordDict转换为哈希集合实现O(1)时间的单词查找初始化dp数组长度为n1全部设为falsedp[0]设为true外层循环遍历所有可能的结束位置i1到n内层循环遍历所有可能的分割点j0到i-1如果dp[j]为true且s[j..i-1]在字典中则设置dp[i]true并跳出内层循环最终返回dp[n]3. 代码实现与优化3.1 基础Python实现def 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]3.2 优化思路内层循环优化不必每次都从0开始检查可以只检查可能存在的单词长度先计算字典中单词的最大长度max_len内层循环j只需要从max(0, i-max_len)开始提前终止如果已经找到dp[i]true可以立即跳出内层循环优化后的实现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]4. 复杂度分析与边界情况4.1 时间复杂度基础版本O(n^2) - 双重循环优化版本O(n * m)其中m是字典中最长单词的长度字典查找O(1)使用哈希集合4.2 空间复杂度O(n) - 用于存储dp数组 O(m) - 存储字典单词集合m是字典中所有字符总数4.3 边界情况处理空字符串应返回true字典为空除非s也是空否则返回false字典中包含空字符串需要特别处理字符串中包含字典中没有的字符可以通过预处理快速判断5. 常见错误与调试技巧5.1 典型错误索引错误混淆字符串的0-based和dp数组的1-based索引s[j:i]对应的是dp[j]和dp[i]的关系确保dp数组长度是n1字典处理不当忘记将列表转换为集合导致查找效率低下没有处理字典为空的情况初始化错误忘记初始化dp[0]true错误地将整个dp数组初始化为true5.2 调试技巧打印dp数组观察每个位置的取值是否符合预期print([(i, val) for i, val in enumerate(dp)])小规模测试先用简单案例验证s a, wordDict [a]s ab, wordDict [a, b]极端情况测试长字符串重复模式s aaa...aaa, wordDict [a]字典单词长度差异大s superlongword, wordDict [super, long, word]6. 实际应用与变种问题6.1 实际应用场景自然语言处理分词、拼写检查编译器设计词法分析阶段识别token密码破解字典攻击中的组合尝试文本处理自动换行算法中的单词分割6.2 相关问题变种返回所有可能的拆分方式力扣第140题需要使用回溯法记录所有路径结合记忆化优化避免重复计算按字典单词的最大分割修改dp数组记录最大分割数状态转移时选择最大值单词拆分II要求使用所有字典单词需要额外记录哪些单词已被使用变成二维动态规划问题7. 个人解题心得在实际解决这个问题时我有几点深刻体会从暴力解法入手即使知道暴力解法效率不高先实现它有助于理解问题本质再思考如何优化。画图辅助在纸上画出dp数组的变化过程能直观理解状态转移的逻辑。测试驱动开发先写测试用例包括各种边界情况再逐步实现算法确保每一步都正确。优化要有依据不要过早优化先确保基础解法正确再分析瓶颈进行针对性优化。理解问题变种掌握基础解法后思考如何适应问题的各种变种这能加深对算法本质的理解。这个问题的核心在于识别出重叠子问题并找到最优子结构是学习动态规划的经典案例。通过这个问题我更加理解了如何将一个问题分解为更小的子问题并利用已解决的子问题来构建最终解。
