LC139. 单词拆分

题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1： 输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2： 输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。

注意，你可以重复使用字典中的单词。

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

提示： 1 <= s.length <= 300 1 <= wordDict.length <= 1000 1 <= wordDict[i].length <= 20 s 和 wordDict[i] 仅由小写英文字母组成 wordDict 中的所有字符串 互不相同

题目解析

好的，没问题！我是 AlgoMooc 的算法老师。我们一起来把这道题啃下来，保证让你这个零基础的新手也能听得明明白白。

---

### 题目在说什么

简单来说，就是给你一个字符串 s，比如 "leetcode"，再给你一个单词列表 wordDict，比如 ["leet", "code"]。你要判断，能不能用这个单词列表里的单词，像拼积木一样，一个接一个地拼出 s 这个字符串。

• 可以重复使用：列表里的单词，你想用几次就用几次。
• 不用全部用完：列表里可能有很多单词，你用其中一部分拼出来就行。
• 必须完全匹配：拼出来的结果，要跟 s 一模一样，不能多也不能少。

举个生活中的例子：你有一盒乐高积木（wordDict），现在想拼出一辆小汽车（s）。你只需要从盒子里找出几个合适的积木块，把它们拼在一起，刚好能组成小汽车的形状就行了。你不需要把盒子里所有积木都用上，而且同一个形状的积木你可以用好几次。

---

### 思路是怎么来的

很多新手看到这种题，第一反应是：“我能不能从 s 的开头，一个一个单词地试过去？” 这个想法很棒，但直接做会很麻烦，因为要尝试很多种组合。

那有没有更聪明的方法呢？我们换个角度想问题。

核心思想：把大问题拆成小问题。

假设我们想知道整个字符串 "leetcode" 能不能被拼出来。我们可以先想：

1. 如果 "leet" 能被拼出来，而且 "code" 刚好在单词列表里，那么 "leetcode" 就能被拼出来。 2. 那 "leet" 能不能被拼出来呢？我们又可以想：如果 "le" 能被拼出来，而且 "et" 在单词列表里... 等等。

你看，我们就把一个长字符串的问题，变成了一个“前缀”字符串的问题。这个“前缀”字符串也是同样的问题。

动态规划 就是专门用来解决这类“大问题可以拆成相同结构的小问题”的利器。

生活化的比喻：搭积木的“地基”

想象一下，你要用积木搭一座桥（字符串 s）。你从桥的一头开始搭。

• dp[i] 表示：从桥头到第 `i` 个桥墩的位置，这一段桥面是否已经搭好了？
• 一开始，dp[0] = true，表示桥头位置（空桥面）是天然搭好的，是我们的起点。
• 现在，你站在一个已经搭好的桥墩 i 上（dp[i] = true）。你环顾四周，看看有没有一块积木（单词），它的长度刚好能让你搭到下一个桥墩 j。
• 如果找到了这样一块积木（s[i:j] 在 wordDict 里），那么你就成功地把桥面延伸到了 j 这个位置，所以 dp[j] = true。

我们就这样，从桥头开始，一步一步地往前探路，把能到达的桥墩都标记为“已搭好”。最后，如果最远的那个桥墩 n（字符串的末尾）被标记为“已搭好”，就说明整座桥都搭成了！

---

### 代码逐步拆解

现在，我们一句一句地看代码，看看它是怎么实现这个“搭桥”过程的。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 1. 把单词列表变成“快速查找”的集合
        Set<String> wordSet = new HashSet<>(wordDict);
        // 为什么要转成 Set？因为从 Set 里找一个单词，速度非常快（O(1)）。
        // 如果直接用 List，每次都要从头到尾找一遍，会很慢。

        int n = s.length();  // 获取字符串 s 的长度，也就是桥的总长度

        // 2. 创建“桥墩状态”数组 dp
        boolean[] dp = new boolean[n + 1];
        // dp[i] 表示：从字符串开头到索引 i-1 的位置（即 s[0:i]），能否被拼出来。
        // 注意：dp 的长度是 n+1，因为我们要记录从 0 到 n 这 n+1 个位置的状态。
        // dp[0] 对应空字符串 ""，dp[n] 对应整个字符串 s。

        // 3. 初始化：空字符串总是可以被拼出来的（不选任何单词）
        dp[0] = true;

        // 4. 开始“搭桥”！
        // 外层循环：遍历每一个可能已经搭好的桥墩 i
        for (int i = 0; i <= n; i++) {
            // 关键剪枝：如果当前桥墩 i 本身都没搭好，那从这里出发是没意义的。
            // 我们只从“已经搭好的桥墩”出发，去寻找下一块积木。
            if (!dp[i]) {
                continue;  // 跳过这个 i，去看下一个
            }

            // 内层循环：从当前桥墩 i 出发，看看能搭到哪个下一个桥墩 j
            // j 的范围是从 i+1 到 n，因为我们要找的单词至少长度为 1。
            for (int j = i + 1; j <= n; j++) {
                // 关键判断：从 i 到 j 的这一段字符串 s[i:j]，是不是单词列表里的一个单词？