（LeetCodeHot100）139. 单词拆分——word-break

zhangzhang2025-12-192025-12-19

139. 单词拆分——word-break

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

1
2
3

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

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

1 2	输入: 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 中的所有字符串 互不相同

我想到了：

1	substring(int beginIndex, int endIndex)

功能：截取区间 [beginIndex, endIndex) 的字符串（包含 beginIndex，不包含 endIndex）
但是我写的时候没想到是包头不包尾
我调试的时候才看出来（今天还是进步了，没用ai改）

我的改正过后部分正确答案

static class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int startIndex = 0;
        int endIndex = 0;
        return find(wordDict, startIndex, endIndex, s);
    }

    private boolean find(List<String> wordDict, int startIndex, int endIndex, String s) {
        String sub = s.substring(startIndex, endIndex);
        if (endIndex < s.length() && !wordDict.contains(sub)) {
            // 如果当前长度的字符不在字典里面，就继续扩大长度去找
            return find(wordDict, startIndex, endIndex+1, s);
        } else if (wordDict.contains(s.substring(startIndex, endIndex))) {
            // 如果找到了
            if (endIndex-1 == s.length() - 1) {
                // 且都找完了，就直接结束，成功了
                return true;
            } else {
                // 还没找完就继续找
                return find(wordDict, endIndex, endIndex+1, s);
            }
        } else {
            // 如果都不是就失败了
            return false;
        }
    }
}

调试代码：

package com.example.leetcode;

import java.util.ArrayList;
import java.util.List;

public class WordBreak {
    static class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            int startIndex = 0;
            int endIndex = 0;
            return find(wordDict, startIndex, endIndex, s);
        }

        private boolean find(List<String> wordDict, int startIndex, int endIndex, String s) {
            String sub = s.substring(startIndex, endIndex);
            if (endIndex < s.length() && !wordDict.contains(sub)) {
                // 如果当前长度的字符不在字典里面，就继续扩大长度去找
                return find(wordDict, startIndex, endIndex+1, s);
            } else if (wordDict.contains(s.substring(startIndex, endIndex))) {
                // 如果找到了
                if (endIndex-1 == s.length() - 1) {
                    // 且都找完了，就直接结束，成功了
                    return true;
                } else {
                    // 还没找完就继续找
                    return find(wordDict, endIndex, endIndex+1, s);
                }
            } else {
                // 如果都不是就失败了
                return false;
            }

        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        List<String> list = new ArrayList<>();
        list.add("leet");
        list.add("code");
        System.out.println(s.wordBreak("leetcode", list));

    }
}

错误样例：

输入

1 2	s ="aaaaaaa" wordDict =["aaaa","aaa"]

输出

false

预期结果

true

调试过后，我知道为什么false了
因为第一个aaa的时候，成功在字典里面找到，继续还有aaaa，但是到aaa的时候发现已经找到了，再找就是在字典里面去找a，但是没有
我想到了回溯，但是我没想到往哪里加

官方解答

是在是妙

方法一：动态规划

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        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] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

复杂度分析

时间复杂度：O(n2) ，其中 n 为字符串 s 的长度。我们一共有 O(n) 个状态需要计算，每次计算需要枚举 O(n) 个分割点，哈希表判断一个字符串是否出现在给定的字符串列表需要 O(1) 的时间，因此总时间复杂度为 O(n2)。
空间复杂度：O(n) ，其中 n 为字符串 s 的长度。我们需要 O(n) 的空间存放 dp 值以及哈希表亦需要 O(n) 的空间复杂度，因此总空间复杂度为 O(n)。

详细解释

我们要解决的问题：给一个字符串 s（比如 “leetcode”）和一个单词字典（比如 [“leet”,”code”]），判断 s 能不能切成若干段，每一段都在字典里存在。

第一步：先搞懂「dp [i]」到底是什么？（最关键的 “备忘录”）

把 dp 想象成一个 “备忘录数组”，每个 dp[i] 记录一个 “小结论”：

i 代表「字符串 s 的前 i 个字符」（比如 i=4，就是 s 从开头到第 4 个字符，也就是 s[0]~s[3]）；
dp[i]的值是true或false：

✅true= 这段 “前 i 个字符的子串” 能拆成字典里的单词；

❌false= 这段子串拆不了。

举个具体例子：

如果 s = "leetcode"（长度 8），那么：

dp[0]：前 0 个字符 → 空串；
dp[4]：前 4 个字符 → 子串 “leet”；
dp[8]：前 8 个字符 → 整个字符串 “leetcode”。

第二步：边界条件「dp [0] = true」—— 为啥空串算 “合法”？

这是个「启动开关」，就像跑步的 “起点线”：

空串本身不需要拆（没有字符要匹配），所以我们默认它 “合法”（dp[0] = true）；
没有这个起点，后面的判断都没法开始（比如要判断 “leet” 合法，得先假设 “空串 + leet” 是合法组合）。

第三步：转移方程「dp [i] = dp [j] && check (s [j..i-1])」—— 怎么用 “旧结论” 推 “新结论”？

这句话翻译成人话：

要判断 “前 i 个字符的子串” 能不能拆（dp [i]），我们可以试着找一个 “切分点 j”，把这段子串切成两部分：

左边：前 j 个字符的子串（s[0]~s[j-1]）→ 它能不能拆，我们早就记在 dp[j] 里了（之前算过）；
右边：从 j 到 i-1 的子串（s[j]~s[i-1]）→ 我们只需要查一下字典，看它在不在里面就行（这就是 check 做的事）。

只要左边合法（dp [j] 是 true），并且右边在字典里（check 是 true），那整个 “前 i 个字符的子串” 就合法（dp [i] = true）！

举个直观例子（手把手算）

假设：

字符串 s = "leetcode"（长度 8）；
字典 wordDict = ["leet", "code"]；
我们要算 dp[8]（整个字符串能不能拆）。

步骤拆解：

我们要找一个切分点 j（j 可以是 0、1、2、…、7），把 “前 8 个字符” 切成「前 j 个字符」和「j 到 7 的子串」；
比如试j=4：
- 左边：前 4 个字符 → 子串 “leet” → 之前算过 dp[4] = true（因为 “leet” 在字典里）；
- 右边：j=4 到 i-1=7 → 子串 “code” → 查字典，在里面（check=true）；
左边合法 + 右边在字典 → dp[8] = true → 整个字符串能拆！

第四步：遍历顺序 + 哈希表优化 —— 让计算更顺、更快

1. 遍历顺序：从左到右算 dp

因为要算 dp[i]，必须先知道所有 dp[0]~dp[i-1] 的结果（左边的 “小结论” 都得有），所以我们从 i=1 开始，一直算到 i = s.length()（整个字符串）。

2. 哈希表优化：查字典更快

把字典里的单词都放进一个哈希集合（比如 HashSet），这样查 “右边子串在不在字典里” 就是瞬间的事（比一个个遍历字典快多了）。

第五步：剪枝（可选，简单提一下）

如果字典里最长的单词是 5 个字符，那 “右边子串” 的长度肯定不能超过 5（超过了字典里没有，没必要查）。所以枚举 j 的时候，从 i-1 倒着往回找，只要 i-j > 最长单词长度，就停止枚举，省时间。

最后：把整个逻辑串成 “步骤流程”（傻瓜式操作）

假设 s = "applepenapple"，字典 ["apple","pen"]，我们按步骤算：

初始化 dp 数组：dp[0] = true（空串合法），其他 dp[1]~dp[13]（因为 s 长度 13）默认都是 false；
算dp[1]（前 1 个字符 “a”）：
- 枚举 j=0：右边子串 “a” → 不在字典 → dp [1] = false；
算dp[2]

（前 2 个字符 “ap”）：
- 枚举 j=0：右边 “ap” 不在字典；j=1：右边 “p” 不在字典 → dp [2] = false；
  
  …
算dp[5]

（前 5 个字符 “apple”）：
- 枚举 j=0：右边 “apple” 在字典，且 dp [0] = true → dp [5] = true；
算dp[8]

（前 8 个字符 “applepen”）：
- 枚举 j=5：右边 “pen” 在字典，且 dp [5] = true → dp [8] = true；
算dp[13]

（整个字符串 “applepenapple”）：
- 枚举 j=8：右边 “apple” 在字典，且 dp [8] = true → dp [13] = true；
最终 dp[13] = true → 字符串能拆！