LeetCode 140. 单词拆分 II

2026-04-02 HGNULB 约 6 分钟

文章信息 9 个分类 7 个标签

分类

LeetCode CodeTop 困难未解决 5-10 腾讯字节阿里微软

题目描述

✅ 140. 单词拆分 II

题意分析

将字符串完整地拆成词典中的单词，保持字符顺序且不遗漏任何字符，返回所有可能的句子，每个句子用空格连接选出的单词。同一个词典单词允许重复使用，答案顺序不限。

这里只能在原字符串的字符间切分，不能增删或重排字符。与只判断能否拆分不同，本题要保留全部合法切法；没有任何完整拆分时，返回空列表。

解法：记忆化 DFS 枚举所有后缀句子

核心思路

[!blue]

定义 dfs(start) 返回后缀 s[start:] 的全部合法句子。它只取决于剩下哪些字符，与前面通过哪些单词到达这个位置无关，所以不同前缀可以共享同一个后缀的计算结果。

从 start 开始枚举单词终点 end。若 s[start:end] 不在词典中，这一段不能作为当前第一个词；若在词典中，就递归取得 dfs(end)，把当前单词分别接到每个后缀句子之前。所有完整切法都有一个唯一的首词终点，枚举全部终点、再组合全部后缀结果，就不会漏掉答案。

到达字符串末尾时，返回只含一个空字符串的列表。它表示“剩余部分已经用完，有一种完成方式”，让最后一个单词可以与这个空后缀组合成完整结果。空列表则表示根本没有完成方式，调用方不应产生任何句子，两种结果不能混淆。

用起点作为记忆化键，缓存对应的整份句子列表，包括无解的空列表。后续分支到达相同起点时直接复用，避免反复枚举相同的后缀。组合时生成新字符串，不修改缓存里的列表或后缀内容，否则其他前缀的结果会被污染。

每次递归的 end 都大于 start，所以不断向字符串末尾前进，能够终止。记忆化减少的是重复展开；如果合法切法本来很多，生成和保存所有答案仍然需要与输出规模相应的时间和空间。

解题步骤

将词典放入哈希集合，创建按后缀起点索引的缓存，从 dfs(0) 开始。

进入某个起点时先查缓存；若起点等于字符串长度，返回包含一个空字符串的列表。

枚举从 start + 1 到字符串末尾的所有 end，取当前前缀作为候选词。

候选词在词典中时，取得 dfs(end) 的全部结果，并逐个组合到当前词后面。

后缀非空时用一个空格连接；后缀为空时只保存当前词，避免尾部多出空格。

缓存当前起点的完整列表，无解时也缓存空列表，最后返回它。

代码实现

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> words = new HashSet<>(wordDict);

        return dfs(s, 0, words, new HashMap<>());
    }

    // 缓存的是从当前下标开始的全部句子，与前面如何切分无关。
    private List<String> dfs(
            String s, int start, Set<String> words, Map<Integer, List<String>> memo) {
        if (memo.containsKey(start)) {
            return memo.get(start);
        }

        // 末尾空串表示一种完成方式，空列表才表示无解。
        if (start == s.length()) {
            List<String> base = new ArrayList<>();

            base.add("");

            return base;
        }

        List<String> sentences = new ArrayList<>();

        for (int end = start + 1; end <= s.length(); end++) {
            String word = s.substring(start, end);

            if (!words.contains(word)) {
                continue;
            }

            for (String suffix : dfs(s, end, words, memo)) {
                sentences.add(suffix.isEmpty() ? word : word + " " + suffix);
            }
        }

        // 无解的空结果也要缓存，后续分支不能反复搜索同一个失败后缀。
        memo.put(start, sentences);

        return sentences;
    }
}

func wordBreak(s string, wordDict []string) []string {
    words := make(map[string]struct{}, len(wordDict))
    for _, word := range wordDict {
        words[word] = struct{}{}
    }

    memo := make(map[int][]string)
    var dfs func(int) []string
    // 缓存的是从当前下标开始的全部句子，与前面如何切分无关。
    dfs = func(start int) []string {
        if sentences, ok := memo[start]; ok {
            return sentences
        }
        // 末尾空串表示一种完成方式，空列表才表示无解。
        if start == len(s) {
            return []string{
                "",
            }
        }

        sentences := make([]string, 0)
        for end := start + 1; end <= len(s); end++ {
            word := s[start:end]
            if _, ok := words[word]; !ok {
                continue
            }

            for _, suffix := range dfs(end) {
                if suffix == "" {
                    sentences = append(sentences, word)
                } else {
                    sentences = append(sentences, word+" "+suffix)
                }
            }
        }

        // 无解的空结果也要缓存，后续分支不能反复搜索同一个失败后缀。
        memo[start] = sentences
        return sentences
    }

    return dfs(0)
}

复杂度分析

设 $n$ 为字符串长度，$M$ 为词典总字符数，$R$ 为所有记忆化结果中实际生成的字符串字符总量。

时间复杂度：$O(M+n^3+R)$。共有 $O(n)$ 个起点，每个起点枚举 $O(n)$ 个终点，截取和哈希子串最坏需要 $O(n)$；生成答案的复制成本计入 $R$。

空间复杂度：$O(M+n+R)$。词典、递归栈和记忆化结果分别对应这三项；最终答案也包含在 $R$ 中。

关键点总结

[!green]

缓存的是后缀的全部句子，不是某条路径上的临时前缀，也不是可行性布尔值。

列表 [''] 表示一条已完成路径，空列表表示无解，它们在组合中作用相反。

首词终点覆盖全部选择，后缀缓存复用重复工作，字符串拼接则承担实际输出成本。

易错点总结

[!yellow]

末尾返回空列表，调用方就没有后缀结果可以组合，连一个单词覆盖全串的切法也会丢失。

与空后缀拼接时仍加入空格，会产生结尾多余空格。

终点枚举不包含字符串长度，永远无法选择覆盖到最后一个字符的单词。

仅缓存有解列表，无解后缀仍可能被多个前缀反复搜索。

用列表长度判断缓存是否命中，会把已缓存的无解状态误当成未计算；应判断键是否存在。

直接修改缓存返回的列表，会让同一个后缀服务其他前缀时带上不属于它的内容。

只因起点有线性数量就声称整体多项式复杂度，会忽略可能指数增长的句子数量。

相似题目

题目	难度	关联与区别
139. 单词拆分	中等	先求可拆分状态可为枚举剪枝，本题还需保存每一种分段结果。
131. 分割回文串	中等	同样枚举所有字符串划分，本题每段需在字典中，原题每段需为回文。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/95173637

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！