139. 单词拆分

单词拆分（Word Break），是一个经典的 动态规划（Dynamic Programming） 问题。

🧠 问题理解

• 给定字符串 s 和字典 wordDict（一个字符串列表）
• 判断是否能将 s 拆分成若干个 字典中存在的单词（可重复使用，不必全用）
• 例如：
  • s = "leetcode", wordDict = ["leet", "code"] → ✅ 可拆为 "leet" + "code" → 返回 true
  • s = "applepenapple", wordDict = ["apple", "pen"] → ✅ "apple" + "pen" + "apple" → true
  • s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] → ❌ 无法完整拆分 → false

🔍 解题思路：动态规划

我们定义一个布尔数组 dp，其中：

• dp[i] 表示 字符串 s 的前 i 个字符（即 s[0:i]）是否可以被拆分。
• 目标是求 dp[n]，其中 n = s.length()

状态转移：

对于每个位置 i（从 1 到 n）：

• 枚举所有可能的分割点 j（0 ≤ j < i）
• 如果 dp[j] == true（前 j 个字符可拆分），并且子串 s.substring(j, i) 在字典中
• 那么 dp[i] = true

初始化：

• dp[0] = true：空字符串可以被拆分（作为起点）

优化：

• 将 wordDict 转为 HashSet，使查找 O(1)

✅ Java 实现

import java.util.*;

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true; // 空字符串可拆分

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break; // 找到一种拆分即可，无需继续
                }
            }
        }

        return dp[n];
    }
}

⏱️ 复杂度分析

• 时间复杂度：O(n² × m)，其中：

  • n = s.length()
  • 最坏情况下，对每个 i 都要检查 i 个 j，每次 substring 是 O(k)，但 Java 的 substring 在新版本中是 O(k)，不过我们可以认为平均子串长度为常数或合并到 n 中。
  • 更严谨地说：O(n²) 次子串操作，每次子串哈希计算最坏 O(n)，所以最坏 O(n³)，但实际中由于 break 和短单词，效率较高。
  • 若使用 Trie 或 滚动哈希 可进一步优化，但本题 DP 已足够。

• 空间复杂度：O(n + d)，其中 d = wordDict.size()（用于 HashSet）

💡 进阶思考（可选）

• 如果 wordDict 很大，但单词长度有限，可以只枚举 j 从 i - maxLen 到 i - minLen，避免无效检查。
• 也可以用 BFS 或 DFS + 记忆化 解决，但 DP 是最清晰高效的。