LeetCode 139. 单词拆分

约 5 分钟
文章信息 20 个分类 11 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 50-100 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 京东 华为 虾皮 LeetCode 热题 100 面试经典 150 题
标签
数组 字符串 哈希表 动态规划 字典树 记忆化 背包问题 动态规划经典题 完全背包问题 记忆化搜索 Brute-Force Search
目录

题目描述

✅ 139. 单词拆分

image-20250420015616151

image-20250420015630735

题意分析

给定字符串 s 和一个单词字典 wordDict，判断 s 能否被完整切成若干段，使每一段都是字典里的单词。注意两个关键信号：字典中的单词可以重复使用，比如 "applepenapple" 可以用 "apple" 两次；题目只问可行性，不要求给出具体的拆分方案，返回一个布尔值即可。

「完整切分」意味着不能剩下任何字符——s = "catsandog" 里 "cats"、"and"、"dog" 都能找到，但无论怎么切总会剩下一段拼不上，答案就是 false。

数据规模很温和：s 长度不超过 300，字典不超过 1000 个词，单词长度不超过 20。这暗示平方级甚至更高的做法都能通过，但也意味着「查一个子串是否为单词」这个动作会被执行很多次，值得做得快一些。

边界上，s 非空、字典非空且单词互不相同，所以不必处理空串输入；但「空前缀」在推导中是一个真实存在的状态，后面会看到它的作用。

解法：前缀动态规划

核心思路

问题关键：直接回溯会反复判断同一个前缀或后缀，最坏呈指数增长。题目只问是否可拆分，不需要保存具体方案，因此用布尔动态规划最合适。

定义 dp[i] 表示前 i 个字符 s[0..i) 能否被完整拆分，dp[0] = true 表示空前缀可拆。枚举最后一个单词的起点 j；若 dp[j] 为真且 s[j..i) 在字典中，就有 dp[i] = true。

不变量：计算 dp[i] 时，所有更短前缀的答案已经确定；每种合法拆分都有唯一的最后一段，因此枚举 j 不会漏解。字典放入哈希集合，并只回看最长单词长度 maxLen，避免无意义的切分点。

解题步骤

  1. 把字典放入哈希集合，同时求出最大单词长度 maxLen。
  2. 创建 dp[n + 1]，初始化 dp[0] = true。
  3. 从 i = 1 到 n 枚举前缀终点，只枚举 j ∈ [max(0, i - maxLen), i)。
  4. 若 dp[j] 为真且 s[j..i) 在集合中，令 dp[i] = true 并停止枚举当前 i。
  5. 返回 dp[n]。例如 leetcode 在 i = 4 得到 dp[4] = true，随后由 code 转移到 dp[8] = true。

代码实现

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        int maxLen = 0;
        for (String word : wordDict) {
            maxLen = Math.max(maxLen, word.length());
        }

        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;

        for (int i = 1; i <= s.length(); i++) {
            for (int j = Math.max(0, i - maxLen); j < i; j++) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.length()];
    }
}

func wordBreak(s string, wordDict []string) bool {
    wordSet := make(map[string]struct{}, len(wordDict))
    maxLen := 0
    for _, word := range wordDict {
        wordSet[word] = struct{}{}
        if len(word) > maxLen {
            maxLen = len(word)
        }
    }

    dp := make([]bool, len(s)+1)
    dp[0] = true
    for i := 1; i <= len(s); i++ {
        start := i - maxLen
        if start < 0 {
            start = 0
        }
        for j := start; j < i; j++ {
            _, exists := wordSet[s[j:i]]
            if dp[j] && exists {
                dp[i] = true
                break
            }
        }
    }

    return dp[len(s)]
}

复杂度分析

  • 时间复杂度：$O(nW^2)$，W 是最大单词长度；每个终点最多检查 W 个子串，构造并哈希子串最多需要 $O(W)$。
  • 空间复杂度：$O(n + S)$，S 是字典中全部字符数；不计临时子串。

关键点总结

  • 可行性问题只需布尔状态；转移通过枚举“最后一个单词”连接到更短前缀。
  • dp[0] = true 是第一个单词能够完成转移的起点。
  • 哈希集合负责快速判词，maxLen 负责缩小切分点范围，两者作用不同。
  • 若要求输出所有拆分方案，应在可行性剪枝基础上回溯，不能只保存布尔值。

易错点总结

  • 忘记 dp[0] = true：s="leet"、字典只有 "leet" 时也无法启动转移。
  • 只检查子串在字典中，不检查 dp[j]：catsandog 会把无法到达的前缀接到 dog 上。
  • 贪心选择最长单词：aaab 配 a, aa, aab 会错过 a + aab。
  • 子串边界写错：Java 的 substring(j, i) 和 Go 的 s[j:i] 都是左闭右开。
  • dp 只开 n 个位置或返回 dp[n - 1]：状态按前缀长度定义，必须使用 n + 1 个位置并返回 dp[n]。

相似题目

题目 难度 考察点
140. 单词拆分 II 困难 从判可行升级为输出所有方案，DP 剪枝 + 回溯
472. 连接词 困难 字典自身互拆，需排除单词本身并控制整体规模
322. 零钱兑换 中等 同为完全背包，从布尔可行性变为求最少数量