LeetCode 139. 单词拆分

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

题目描述

✅ 139. 单词拆分

image-20260928194117384

image-20260928194117385

题意分析

给定字符串 s 和字典 wordDict，判断能否把 s 从头到尾划分为若干连续片段，并且每个片段都是字典中的单词。字符不能跳过、重排或重复使用；字典中的单词可以重复使用，也不要求用完所有单词。

本题只返回能否拆分，不需要输出方案或统计方案数。某一段恰好是单词还不够，它前面的整段也必须能够拆分，才能把这个单词接到已有方案后面。

解法：前缀动态规划

核心思路

[!blue]

一次拆分的最后一段一定是字典中的某个单词。把它去掉后，前面剩下的仍然是同样的拆分问题，因此可以按前缀长度做动态规划。

定义 dp[i] 表示前 i 个字符，即 s[0:i]，能否完整拆分。枚举最后一个单词的起点 j：若 dp[j] 为真，且 s[j:i] 在字典中，就能把这个单词接到前 j 个字符的拆分结果之后，令 dp[i] = true。反过来，任何合法拆分都有这样一个最后单词，因此枚举所有可能的 j 不会漏掉方案。

初始化 dp[0] = true，表示空前缀不需要任何单词就已经完成拆分。它是第一个单词的连接起点，而不是说字典中必须包含空字符串。其余状态初始为假，按 i 从小到大计算；因为单词非空，转移只依赖 j < i 的已知状态。

字典用哈希集合保存，便于判断候选片段是否为单词。再记录最长单词长度 maxLen：超过该长度的片段不可能匹配，所以只枚举 max(0, i - maxLen) <= j < i。找到一个可行切分点就足以确定 dp[i]，无须继续枚举其他方案。

不能只选当前能匹配的最长单词，因为它可能让剩余部分无法拆分。动态规划保留所有可到达的前缀长度，最终读取 dp[n]，才能判断整个字符串是否可拆。

解题步骤

  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]，其中 n 为字符串长度。

代码实现

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(S + nW^2)$，其中 S 为字典总字符数，W 为最长单词长度。准备集合需要哈希字典中的字符串；每个终点至多检查 W 个片段，每次构造或哈希片段最多需要 $O(W)$ 时间。Go 的字符串切片不复制字符，但查询哈希集合仍需计算片段的哈希值。
  • 空间复杂度：$O(n + d)$，其中 d 为字典单词数，不计输入本身。dp 占 $O(n)$，集合保存已有字符串的引用或描述信息，占 $O(d)$；Java 查询时产生的临时子串最长不超过 n，不会增大该空间上界。

关键点总结

[!green]

  • 可行性问题只需布尔状态；转移通过枚举“最后一个单词”连接到更短前缀。
  • dp[0] = true 是第一个单词能够完成转移的起点。
  • 哈希集合负责快速判词，maxLen 负责缩小切分点范围，两者作用不同。

易错点总结

[!yellow]

  • 忘记设置 dp[0] = true，所有状态都会因缺少可行前缀而无法启动转移。
  • 只检查最后一段是否在字典中、不检查 dp[j]，会把无法拆分的前缀也算进结果。
  • 匹配到单词后就从集合删除，会错误禁止同一个单词重复使用；每个转移都查询完整字典。
  • Java 的 substring(j, i) 和 Go 的 s[j:i] 都是左闭右开，对应片段长度为 i - j。
  • 状态下标表示前缀长度而非字符下标，必须分配 n + 1 个位置并返回 dp[n]。

相似题目

题目 难度 关联与区别
140. 单词拆分 II 困难 切分可达性相同，原题还要枚举全部句子，本题只需布尔DP。
472. 连接词 困难 同样判断一个词能否由字典词拼成，原题要求至少两个更短词，不能把自身直接当一个匹配。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/14966021
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！