139. 单词拆分#

我第一次遇到 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"

plaintext

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

问题描述#

题目目标#

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict ，判断 s 是否可以被空格拆分为一个或多个在字典中出现的单词。字典中的单词可以重复使用。

示例 1#

输入： s = "leetcode", wordDict = ["leet","code"] 输出： true 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

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

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

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

// 方法一：朴素递归（会超时）
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)) {
                    // 只要有一种切分方式成功，就可以直接返回 true
                    return true;
                }
            }
        }
        // 所有单词都尝试后仍失败，说明当前字符串无法拆分
        return false;
    }
}

java

第二步：发现问题的本质#

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

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

plaintext

画出递归树，你会发现：

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

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

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

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

状态定义： dp[i] 表示字符串s的前i个字符能否被拆分成字典中的单词
转移方程： dp[i] = dp[j] && check(s[j..i]) 其中j < i，check函数判断子串s[j..i]是否在字典中
边界情况： dp[0] = true，表示空字符串可以被拆分

// 方法二：动态规划（最终优化版本）
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 将字典转为 HashSet，把“是否包含某个单词”的查询降为 O(1) 平均复杂度
        Set<String> dict = new HashSet<>(wordDict); // 转换成Set提高查询效率
        // dp[i] 表示 s 的前 i 个字符（即 s[0..i-1]）能否被字典拆分
        boolean[] dp = new boolean[s.length() + 1];
        // 边界状态：空字符串一定可以被拆分
        dp[0] = true; // 空字符串总是可以被拆分的

        // 外层循环：枚举前缀长度 i，逐步求出 dp[1..n]
        for (int i = 1; i <= s.length(); i++) {
            // 内层循环：枚举分割点 j，把前缀拆成 s[0..j-1] 和 s[j..i-1]
            for (int j = 0; j < i; j++) {
                // 转移条件：前半段可拆分 + 后半段是字典单词
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    // 只要找到一个合法分割点，当前前缀就可拆分
                    dp[i] = true;
                    // 当前 i 已经确定为 true，无需继续检查其它 j
                    break; // 找到一种可行的拆分方式就可以了
                }
            }
        }

        // 返回完整字符串 s（长度为 s.length()）是否可拆分
        return dp[s.length()];
    }
}

java

第四步：优化细节#

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

// 方法三：优化后的动态规划
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 使用 Set 提升字典查找效率
        Set<String> dict = new HashSet<>(wordDict);
        // dp[i]：前 i 个字符是否可拆分
        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());
        }

        // i 从 minLen 开始，长度不足 minLen 的前缀一定不可能匹配任何单词
        for (int i = minLen; i <= s.length(); i++) {
            // j 的下界是 i-maxLen，避免检查过长子串；上界保持 j < i
            for (int j = Math.max(0, i - maxLen); j < i; j++) {
                // 若前缀 s[0..j-1] 可拆分，且 s[j..i-1] 在字典中，则 dp[i] 为真
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    // 找到一个可行拆分即可确定当前状态
                    dp[i] = true;
                    // 无需继续尝试其他分割点
                    break;
                }
            }
        }

        // 返回整个字符串是否可以被拆分
        return dp[s.length()];
    }
}

java

🔍 解题技巧与优化思路#

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

💡 举一反三#

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

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

🎯 思考题#

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

🎓 面试指南#

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

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

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

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