LeetCode 139：单词拆分（Word Break）题解

Word Break 是 LeetCode Hot 100 里面一道非常经典的动态规划题。

这道题表面上看起来只是“判断一个字符串能不能被拆开”，但真正做起来时，很多人都会卡在一个问题上：

当我们在某个位置拆开以后，前面的部分到底是不是也一定合法？

也就是说，这道题的关键并不是单纯看某一个子串是否在字典里，而是要同时满足两件事：

1. 当前这一段子串在字典中出现过；

2. 当前这一段前面的前缀部分，也能够被成功拆分。

你给出的这份 Java 代码，使用的是这道题非常实用、也很好理解的一种写法：

记忆化搜索 + 哈希集合优化查找

这种写法本质上是“自顶向下”的动态规划。

它的核心思路非常清晰：

• 设 dfs(i) 表示字符串前 i 个字符能否被成功拆分；

• 枚举最后一个单词的起点 j；

• 如果 s[j, i) 在字典中，并且 dfs(j) 也成立，那么 dfs(i) 就成立。

本文就结合你这段代码，系统地讲一下这道题的解题思路。

一、题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。

请你判断是否可以利用字典中出现的单词拼接出 s。

注意：

• 字典中的单词可以重复使用；

• 不要求按照字典顺序使用；

• 只需要判断能不能拆分成功，不需要返回具体拆分方案。

二、示例分析

示例 1

输入：s = "leetcode", wordDict = ["leet", "code"]
输出：true

因为：

"leetcode" = "leet" + "code"

所以返回 true。

示例 2

输入：s = "applepenapple", wordDict = ["apple", "pen"]
输出：true

因为：

"applepenapple" = "apple" + "pen" + "apple"

注意这里的 apple 被重复使用了，这是允许的。

示例 3

输入：s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出：false

虽然里面有很多局部单词能匹配上，比如：

• cat

• cats

• and

• sand

• dog

但是整个字符串始终无法完整拼接出来，所以最终返回 false。

三、为什么会想到记忆化搜索

看到这道题，最容易想到的方法就是：

从后往前或者从前往后不断尝试切分。

比如对于字符串 leetcode，我们可以尝试：

• 最后一个单词是不是 e？

• 是不是 de？

• 是不是 ode？

• ……

• 是不是 code？

当我们发现 code 在字典里时，就继续递归判断前面的 leet 能不能被拆分。

这种思路本身没有问题，但如果不做优化，会出现大量重复计算。

举个例子：

某个前缀 s[0...j) 可能会被很多不同的拆分路径反复判断。

所以这里就很自然地想到：

把已经计算过的位置记录下来，避免重复递归。

这就是记忆化搜索。

四、状态设计

你这份代码的状态定义非常清楚：

private int dfs(int i, int maxLen, String s, Set<String> words, int[] memo)

其中：

• i 表示当前要判断的是字符串前 i 个字符，即区间 s[0, i)；

• 返回值为：

  • 1：可以拆分；

  • 0：不可以拆分；

  • -1：还没有计算过。

也就是说：

dfs(i) = 前 i 个字符能否由字典中的单词拼接而成

当 i == 0 时，说明前缀为空串。

空串显然可以认为是“已经成功拆分完成”的状态，所以返回 1。

这就是递归的边界。

五、转移过程

对于 dfs(i)，我们要思考的是：

最后一个单词可能是哪一段？

假设最后一个单词是 s[j, i)，那么要想让 dfs(i) 成立，必须满足：

1. s[j, i) 在字典中；

2. dfs(j) 为真，也就是 s[0, j) 能被成功拆分。

因此转移逻辑就是：

dfs(i) = 是否存在某个 j，满足：
         s[j, i) 在字典中，并且 dfs(j) == true

这正是你代码中的这一段：

for (int j = i - 1; j >= Math.max(i - maxLen, 0); j--) {
    if (words.contains(s.substring(j, i)) && dfs(j, maxLen, s, words, memo) == 1) {
        return memo[i] = 1;
    }
}

只要找到一个合法切分点 j，就说明当前位置可以被拆分，直接返回成功。

如果所有可能的 j 都试过了还不行，就返回失败。

六、为什么要先求 maxLen

这是你这份代码里一个很值得学习的优化点。

先看这段代码：

int maxLen = 0;
for (String word : wordDict) {
    maxLen = Math.max(maxLen, word.length());
}

它的作用是求出字典中最长单词的长度。

为什么这样做有意义？

因为如果字典里最长的单词长度只有 5，那么对于某个位置 i 来说，最后一个单词的长度绝对不可能超过 5。

也就是说，我们在枚举切分点 j 时，没有必要一直枚举到 0，只需要枚举到：

i - maxLen

这样就把很多无意义的判断直接剪掉了。

所以这段循环写成了：

for (int j = i - 1; j >= Math.max(i - maxLen, 0); j--)

这个优化虽然不改变算法本质，但在实际运行时会更高效。

七、为什么要把 wordDict 转成 HashSet

你代码中还有一个关键处理：

Set<String> words = new HashSet<>(wordDict);

这是因为我们会频繁判断某个子串是否在字典中。

如果直接用 List 去查找，那么每次都需要线性扫描，效率较低。

而 HashSet 的平均查询时间复杂度是 O(1)，可以大幅提升查找效率。

所以在这类“频繁判断某个元素是否存在”的题目里，把列表转成哈希集合通常都是标准操作。

八、记忆化数组的作用

代码中这部分：

int[] memo = new int[n + 1];
Arrays.fill(memo, -1);

含义是：

• memo[i] = -1：还没算过；

• memo[i] = 0：前 i 个字符不能拆分；

• memo[i] = 1：前 i 个字符可以拆分。

在递归时：

if (memo[i] != -1) {
    return memo[i];
}

这一步就能直接复用之前的结果，避免重复搜索。

例如某个 dfs(5) 已经判断过失败了，那么以后再遇到 dfs(5)，就不用再把所有切分情况重新试一遍。

这就是“记忆化”的价值所在。

九、执行过程举例

下面用这个例子来走一遍流程：

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

首先：

• maxLen = 4

• words = {"leet", "code"}

• 调用 dfs(8)，表示判断 "leetcode" 能不能拆分。

第一步：判断 dfs(8)

枚举最后一个单词的起点 j：

• j = 7，子串是 "e"，不在字典中；

• j = 6，子串是 "de"，不在字典中；

• j = 5，子串是 "ode"，不在字典中；

• j = 4，子串是 "code"，在字典中。

于是递归判断：

dfs(4)

第二步：判断 dfs(4)

继续枚举最后一个单词：

• j = 3，"t" 不在字典中；

• j = 2，"et" 不在字典中；

• j = 1，"eet" 不在字典中；

• j = 0，"leet" 在字典中。

于是递归判断：

dfs(0)

第三步：判断 dfs(0)

i == 0，说明已经成功拆分到空串，返回 1。

于是：

• dfs(4) = 1

• dfs(8) = 1

最终返回 true。

十、代码详解

下面是你给出的代码，我加上详细注释后如下：

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 先求出字典中最长单词长度，后面做剪枝优化
        int maxLen = 0;
        for (String word : wordDict) {
            maxLen = Math.max(maxLen, word.length());
        }

        // 用 HashSet 存储字典，加快查找速度
        Set<String> words = new HashSet<>(wordDict);

        int n = s.length();

        // memo[i] 表示前 i 个字符能否拆分
        // -1：未计算
        //  0：不能拆分
        //  1：可以拆分
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);

        return dfs(n, maxLen, s, words, memo) == 1;
    }

    private int dfs(int i, int maxLen, String s, Set<String> words, int[] memo) {
        // 递归边界：空串可以认为拆分成功
        if (i == 0) {
            return 1;
        }

        // 如果已经计算过，直接返回结果
        if (memo[i] != -1) {
            return memo[i];
        }

        // 枚举最后一个单词的起点 j
        // 由于最长单词长度为 maxLen，所以 j 不需要枚举得太远
        for (int j = i - 1; j >= Math.max(i - maxLen, 0); j--) {
            // 如果 s[j, i) 在字典里，并且前 j 个字符也能拆分
            if (words.contains(s.substring(j, i)) && dfs(j, maxLen, s, words, memo) == 1) {
                return memo[i] = 1;
            }
        }

        // 所有情况都试过，仍然不能拆分
        return memo[i] = 0;
    }
}

十一、复杂度分析

时间复杂度

设字符串长度为 n，字典中最长单词长度为 L。

对于每个位置 i，最多会枚举 L 个切分点。

同时由于有记忆化，每个状态只会计算一次，因此总的状态数是 n 个。

所以整体时间复杂度可以写成：

O(n * L)

严格来说，substring 在某些语言实现里还会带来额外开销，但在算法分析时，一般核心思路仍然记作 O(n * L)。

空间复杂度

• memo 数组需要 O(n)；

• HashSet 存储字典需要 O(m)，其中 m 为字典总大小；

• 递归调用栈最深可能达到 O(n)。

所以整体空间复杂度通常写作：

O(n + m)

如果只关注和字符串长度相关的额外状态空间，也可以理解为 O(n)。

十二、这道题和动态规划的关系

虽然你这份代码写的是递归，但它本质上仍然是动态规划。

因为它满足动态规划最核心的两个条件：

1. 最优子结构

如果前 i 个字符可以拆分，那么它一定可以表示成：

• 前 j 个字符可以拆分；

• 再加上一个合法单词 s[j, i)。

也就是说，大问题依赖小问题。

2. 重复子问题

很多不同的拆分路径，都会重复访问同一个 dfs(j)。

这就说明用记忆化搜索或者自底向上的 DP 都是可行的。

因此这题其实有两种主流写法：

• 记忆化搜索（自顶向下）

• 动态规划（自底向上）

你现在这份代码属于第一种。

这种写法的优点是：

• 思路更接近“切分”的直觉；

• 代码逻辑清晰；

• 配合记忆化后效率也很不错。

十三、总结

这道题最核心的点，不是简单判断某个子串是否在字典里，而是要判断：

整个前缀是否能够被合法拆分。

你这份代码的解法可以概括为：

1. 先把字典转成 HashSet，提高查找效率；

2. 再求出字典中最长单词长度，用来剪枝；

3. 用 dfs(i) 表示前 i 个字符能否被拆分；

4. 枚举最后一个单词的起点 j；

5. 用 memo 记录状态，避免重复计算。

这是一种非常标准、也非常值得掌握的写法。

如果你把这道题真正理解透了，那么后面遇到很多“字符串划分”“前缀匹配”“字典拆分”类题目时，都会轻松很多。