单词拆分：动态规划中的字符串处理艺术

我第一次遇到 LeetCode 139 题「单词拆分」时，着实被难住了。这道题不像零钱兑换那样直观，但通过这篇文章，我希望能帮你理解这道经典题目背后的思维逻辑。让我们一起深入探索这个迷人的算法问题。

🎯 问题本质：文字的拼接游戏

想象你是一个文字游戏的设计师，需要判断一个字符串是否能被拆分成字典中的单词。具体来说：

输入：s = "leetcode", wordDict = ["leet", "code"]
输出：true
解释："leetcode" 可以被拆分成 "leet" 和 "code"

输入：s = "applepenapple", wordDict = ["apple", "pen"]
输出：true
解释："applepenapple" 可以被拆分成 "apple" "pen" "apple"

输入：s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出：false
解释：无法用字典中的词拼出 "catsandog"

这个问题乍看简单，但其实暗藏玄机。为什么呢？因为我们不仅要判断单词是否在字典中，还要考虑所有可能的拆分方式。

💡 解题思路：从暴力到优化的进阶之路

第一步：暴力递归（超时是必然的）

最直观的想法是：从字符串的每个位置开始，尝试匹配字典中的单词。如果匹配成功，继续处理剩余部分。

// 方法一：朴素递归（会超时）
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 递归的基本情况：空字符串总是可以被拆分的
        if (s.length() == 0) return true;
        
        // 尝试用字典中的每个单词去匹配字符串的开头
        for (String word : wordDict) {
            // 如果当前单词可以匹配字符串的开头
            if (s.startsWith(word)) {
                // 递归处理剩余的子串
                if (wordBreak(s.substring(word.length()), wordDict)) {
                    return true;
                }
            }
        }
        return false;
    }
}

第二步：发现问题的本质

让我们通过一个例子来理解为什么这个方法会超时：

s = "aaab"
wordDict = ["a", "aa"]

画出递归树，你会发现：

• 第一次选择"a"后，需要处理"aab"
• 第一次选择"aa"后，也需要处理"ab"
• 这些子问题在递归过程中被重复计算了多次

这就是典型的"重叠子问题"！启发我们使用动态规划来优化。

第三步：设计动态规划解法

关键在于设计状态定义和转移方程：

1. 状态定义： dp[i] 表示字符串s的前i个字符能否被拆分成字典中的单词

2. 转移方程： dp[i] = dp[j] && check(s[j..i]) 其中j < i，check函数判断子串s[j..i]是否在字典中

3. 边界情况： dp[0] = true，表示空字符串可以被拆分

// 方法二：动态规划（最终优化版本）
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict); // 转换成Set提高查询效率
        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] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break; // 找到一种可行的拆分方式就可以了
                }
            }
        }
        
        return dp[s.length()];
    }
}

第四步：优化细节

为了进一步提升性能，我们可以添加一些剪枝条件：

// 方法三：优化后的动态规划
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        
        // 找出字典中最长和最短的单词长度
        int maxLen = 0, minLen = Integer.MAX_VALUE;
        for (String word : dict) {
            maxLen = Math.max(maxLen, word.length());
            minLen = Math.min(minLen, word.length());
        }
        
        for (int i = minLen; i <= s.length(); i++) {
            // 只考虑符合长度范围的子串
            for (int j = Math.max(0, i - maxLen); j < i; j++) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[s.length()];
    }
}

🔍 解题技巧与优化思路

1. 使用HashSet存储字典，提高查询效率
2. 记录最大最小单词长度，减少无效的子串检查
3. 当找到一种可行的拆分方式时立即break内层循环
4. 可以考虑使用字符串哈希等技术进一步优化子串判断

💡 举一反三

理解了单词拆分，你会发现很多字符串的动态规划问题都是相通的：

• 回文串的分割
• 正则表达式匹配
• 编辑距离

🎯 思考题

如果要求返回所有可能的拆分方式（LeetCode 140 单词拆分 II），该如何修改我们的代码？这个问题会比当前这个版本难在哪里？

🎓 面试指南

遇到这类字符串动态规划问题，建议这样思考：

1. 先尝试写出递归解法，理解问题的本质
2. 找出重叠子问题，这是使用动态规划的关键依据
3. 设计状态定义，这往往是最难的部分
4. 推导状态转移方程，可以通过具体例子来帮助思考
5. 考虑边界情况，比如空字符串的处理
6. 最后思考优化空间，比如剪枝、哈希等技术

记住，字符串的动态规划题目往往看起来很难，但只要我们能够正确地定义状态，理清楚状态之间的转移关系，就能一步步找到解决方案。

---

作者：忍者算法
公众号：忍者算法

动态规划不仅是一种算法技巧，更是一种解决问题的思维方式。希望通过这道题，能让你对字符串类动态规划问题有更深的理解！

#算法面试 #LeetCode #动态规划 #字符串处理