单词拆分——完全背包字符串版与DFS+记忆化对比

适读人群：Java后端工程师、字符串DP学习者 | 阅读时长：约20分钟 | 难度：Medium

---

开篇故事

单词拆分是一道表面不像背包、本质是背包的题。

我第一次做是用DFS，写了个递归，对每个位置枚举所有单词，看能不能接上。结果超时了——因为有大量重复计算。加了记忆化之后通过了。

后来重新想这道题，突然发现：这不就是完全背包吗？字符串相当于"背包容量"，字典里的每个单词相当于"物品"，每个物品（单词）可以无限次使用（同一个单词可以出现多次）。问题变成：能否用字典里的单词"恰好填满"整个字符串？

背包的框架一套上去，代码立刻清晰了很多，也更容易推广到统计方案数（Word Break II）。

今天把DP和DFS+记忆化两种思路都拆解，让你看清楚它们本质上是同一回事的不同视角。

---

一、题目解析

题号：LeetCode 139. Word Break

题目描述：给你一个字符串 s 和一个字符串列表 wordDict 作为字典，判断是否可以利用字典中出现的单词拼接出 s。注意：字典中同一个单词可以在拼接中被重复使用，字典中没有重复的单词。

示例：

• 输入：s = "leetcode"，wordDict = ["leet","code"]，输出：true
• 输入：s = "applepenapple"，wordDict = ["apple","pen"]，输出：true（apple+pen+apple）
• 输入：s = "catsandog"，wordDict = ["cats","dog","sand","and","cat"]，输出：false

---

二、DP思路推导

2.1 完全背包视角

把 s 看作背包，容量为 s.length()。字典里的每个单词是物品，重量为单词的长度，每个物品可以无限次使用。问题是：能否精确装满背包？

这就是完全背包的可行性问题（布尔版）。

2.2 状态定义

定义 dp[i] = s 的前 i 个字符（s[0..i-1]）能否被字典里的单词拼成

2.3 状态转移方程

对于每个位置 i，考虑最后一个单词是哪个：

如果存在某个 j（0 <= j < i），使得 dp[j] 为 true 且 s[j..i-1] 在字典中，那么 dp[i] = true。

dp[i] = true，如果存在 j(0<=j<i) 使得 dp[j]==true 且 s[j..i-1] in wordDict

2.4 两种等价遍历方式

方式A：外层枚举位置 i，内层枚举单词（完全背包）

for (int i = 1; i <= n; i++) {
    for (String word : wordDict) {
        int len = word.length();
        if (i >= len && dp[i - len] && s.substring(i - len, i).equals(word)) {
            dp[i] = true;
            break;  // 已经找到一种拆分方式，无需继续
        }
    }
}

方式B：外层枚举起点 j，内层枚举终点 i（枚举分割点）

for (int j = 0; j < n; j++) {
    if (!dp[j]) continue;  // 前j个字符不可达，跳过
    for (int i = j + 1; i <= n; i++) {
        if (wordSet.contains(s.substring(j, i))) {
            dp[i] = true;
        }
    }
}

两种方式等价，方式B更容易理解"从可达点出发"的思路。

2.5 边界条件

• dp[0] = true：空字符串，不需要任何单词，直接"拼成"

2.6 状态转移示意

s = "leetcode", wordDict = ["leet", "code"]

dp[0] = true（空串）
dp[1]: 没有长度为1的单词能匹配s[0..0]='l' → false
dp[2]: false
dp[3]: false
dp[4]: dp[0]=true 且 s[0..3]="leet" 在字典中 → dp[4]=true
dp[5]: false
dp[6]: false
dp[7]: false
dp[8]: dp[4]=true 且 s[4..7]="code" 在字典中 → dp[8]=true ✓

---

三、解法一：标准DP（完全背包布尔版）

public class WordBreak {
    
    /**
     * 139. 单词拆分 - DP（完全背包）
     * 时间复杂度：O(n^2 * m)，n=s.length, m=字典总字符数
     * 空间复杂度：O(n)
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        Set<String> wordSet = new HashSet<>(wordDict);
        
        // dp[i] = s[0..i-1]能否由字典中的单词拼成
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;  // 空串可达
        
        // 外层枚举字符串长度（背包容量）
        for (int i = 1; i <= n; i++) {
            // 内层枚举分割点j（上一个可达点）
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[n];
    }
}

优化：利用最大单词长度剪枝

如果字典中最长的单词是 maxLen，那么只需要枚举最近 maxLen 长度范围内的分割点：

public boolean wordBreakOptimized(String s, List<String> wordDict) {
    int n = s.length();
    Set<String> wordSet = new HashSet<>(wordDict);
    int maxLen = 0;
    for (String w : wordDict) maxLen = Math.max(maxLen, w.length());
    
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;
    
    for (int i = 1; i <= n; i++) {
        // 只枚举最近maxLen范围内的分割点
        for (int j = Math.max(0, i - maxLen); j < i; j++) {
            if (dp[j] && wordSet.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    
    return dp[n];
}

---

四、解法二：DFS + 记忆化

/**
 * 139. 单词拆分 - DFS + 记忆化
 * 自顶向下，和DP等价
 */
public boolean wordBreakDFS(String s, List<String> wordDict) {
    Set<String> wordSet = new HashSet<>(wordDict);
    // memo[i]: -1未计算, 0不可行, 1可行
    int[] memo = new int[s.length()];
    Arrays.fill(memo, -1);
    return dfs(s, wordSet, 0, memo);
}

/**
 * 从s[start..]开始，能否被字典里的单词拼成
 */
private boolean dfs(String s, Set<String> wordSet, int start, int[] memo) {
    if (start == s.length()) return true;
    if (memo[start] != -1) return memo[start] == 1;
    
    for (int end = start + 1; end <= s.length(); end++) {
        if (wordSet.contains(s.substring(start, end)) && dfs(s, wordSet, end, memo)) {
            memo[start] = 1;
            return true;
        }
    }
    
    memo[start] = 0;
    return false;
}

DP与DFS+记忆化的对应关系：

两者的计算量完全相同，只是遍历方向相反（DP从0到n，DFS从n递归到0）。

---

五、举一反三

相关题目：

1. LeetCode 140. 单词拆分II：不只是判断能否拆分，还要列出所有拆分方案（DFS回溯+记忆化）
2. LeetCode 472. 连接词：判断字典中哪些单词可以由字典中其他单词组成，对每个词跑一次单词拆分
3. LeetCode 2707. 字符串中的额外字符：单词拆分的变体，允许跳过一些字符

---

六、踩坑实录

坑一：没有用HashSet，用了List做单词查找

如果用 wordDict.contains() 判断单词，每次查找是 O(n×m)，总复杂度爆炸。一定要先把字典转成 HashSet，查找 O(1)。

坑二：substring 的边界

s.substring(j, i) 是左闭右开区间 [j, i)，对应字符串 s[j..i-1]。容易和"前i个字符"（s[0..i-1]）混淆。每次分割检查时，分割点 j 到 i 的子串是 s[j..i-1]，长度是 i-j。

坑三：DFS忘记处理 start==s.length() 的情况

在DFS里，当 start 等于 s.length() 时，说明已经拼完了整个字符串，应该返回 true。如果忘记这个 base case，递归会越界。

坑四：记忆化DFS里memo的初始值

如果用 boolean[] 作为 memo，默认值是 false，无法区分"未计算"和"计算结果为false"。我建议用 int[]，-1表示未计算，0表示不可行，1表示可行，或者用 Boolean[]（引用类型，null表示未计算）。

---

七、总结

单词拆分的核心是认识到它是完全背包（字符串版）：字典单词是物品，字符串是背包，问题是能否精确装满。

DP从0推到n，DFS+记忆化从n递归到0，两种方向的遍历等价。

对于字符串DP，一个重要的优化是利用最大单词长度来限制分割点的枚举范围，把常数因子压缩下来。