139. 单词拆分

📝 题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果 s 可以由字典中若干单词按顺序拼接而成，返回 true；否则返回 false。

注意：

• 字典中的单词可以重复使用。
• 不要求字典中出现的单词都必须用上。

---

📌 示例

示例 1

输入：

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

输出：

true

解释：
leetcode = leet + code

---

示例 2

输入：

s = "applepenapple"
wordDict = ["apple", "pen"]

输出：

true

解释：
applepenapple = apple + pen + apple

---

示例 3

输入：

s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]

输出：

false

---

🚀 最优解：动态规划（字符串切割 DP）

我们定义：

dp[i] = s 的前 i 个字符能否被拼接出来

也就是判断：

从 0 到 i 的子串，能否被字典分割。

初始状态：

dp[0] = true

表示空字符串是可以被拼出来的。

状态转移：

对于 s 的每个前缀 s[0…i)，检查字典中的每个单词 word：

如果 s[i-m, i) == word 且 dp[i-m] == true
→ dp[i] = true

最终返回 dp[n]。

---

✅ 完整代码（Java）

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取字符串s
        String s = scanner.nextLine();

        // 读取字典单词数量
        int m = scanner.nextInt();
        List<String> wordDict = new ArrayList<>();

        // 读取字典单词
        scanner.nextLine(); // 消费换行符
        for (int i = 0; i < m; i++) {
            wordDict.add(scanner.nextLine());
        }

        Solution solution = new Solution();
        boolean result = solution.wordBreak(s, wordDict);

        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for(int i = 1; i <= n; i++){
            for(String word : wordDict){
                int m = word.length();
                if(m <= i){
                    // 如果前面可拆 && 当前子串等于 word
                    if(dp[i - m] && word.equals(s.substring(i - m, i))){
                        dp[i] = true;
                        break;  // 提前退出，已经能拆了
                    }
                }
            }
        }
        return dp[n];
    }
}

---

🧠 通俗易懂解释

把字符串 s 看成一条路，我们从左往右走，只有走到某个位置 i 时，它能被成功拆分，我们才把 dp[i] 标记为 true。

比如：

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

推导过程：

• dp[0] = true
• 检查前 4 字符 "leet" 与字典匹配，并且 dp[0] == true → dp[4] = true
• 检查 "code"（位置 4–8） 与字典匹配，并且 dp[4] == true → dp[8] = true

最终 dp[n] = dp[8] = true。

思路非常类似“跳格子”，只有你能跳过去的位置，才算可达。

---

⏱ 时间复杂度

O(n × k × m)

• n 是字符串长度
• k 是字典大小
• m 是每个单词的平均长度（因为 substring 比较需要 O(m)）

题目约束 wordDict[i] ≤ 20，所以实际非常快。

---

💾 空间复杂度

O(n)

一个长度为 n+1 的 dp 数组。

/dp[i] = 以s(0-i)是否可以被拼出