LeetCode 648. 单词替换

2021-08-11 HGNULB 约 10 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 648. 单词替换

题意分析

要什么：给一个词根表和一个句子，句子里每个单词如果能以词根表中的某个词根作为前缀，就把它替换成那个词根；有多个词根都能匹配时，取最短的那个；一个都匹配不上就原样保留。最后按原顺序拼回句子。
约束透露的信号：判定的是「前缀」而非「子串」或「相等」，而前缀匹配天然对应从根往下走的路径结构；词根数量和句子长度都到 $10^5$ 量级，逐词根逐单词地做 startsWith 是 $O(|dict| \times |words| \times L)$，必然超时。「取最短词根」这个要求尤其关键——它意味着沿着单词的字符往下走时，第一次踩到词根标记就可以立刻停止，不需要走完整个单词再比较长度。
边界：字符集只有小写字母，加上单词间以单个空格分隔；某个词根可能恰好等于整个单词（此时替换后字符串不变）；一个词根可能是另一个词根的前缀（如 a 和 ab），此时短的必须优先；单词长度可能小于所有词根，走不到底就要提前退出；输出必须保持原有的单词顺序和单空格分隔。

解法：Trie（前缀树）

核心思路

暴力做法是对句子中的每个单词，遍历整个词根表逐个判断是否为前缀，再在所有命中的词根里取最短。正确但慢：每次判断本身就是 $O(L)$，总量是三重乘积。
瓶颈在于大量词根共享公共前缀，却被反复比较了无数次。比如词根表里有 cat、car、can，对单词 cattle 做匹配时，前两个字符 c、a 被独立地比对了三遍。
观察到「前缀匹配」这件事只依赖字符序列本身，于是可以把所有词根按字符逐层合并成一棵树：从根出发，每条边代表一个字符，一条从根到某节点的路径就代表一个前缀。共享前缀的词根自动合并成同一条路径，比较一次就服务所有词根。
由此定下数据结构与状态：每个节点持有 26 个子指针，并用一个 word 字段标记「从根到本节点的这条路径是否恰好构成一个完整词根，以及它是哪一个」。查询时的不变量是：沿着待查单词的字符从根往下走，走到第 i 层时，当前节点代表该单词长度为 i 的前缀；一旦某个节点带有词根标记，它就是所有能匹配该单词的词根中最短的那个——因为深度即长度，而我们是自浅入深遍历的，第一个遇到的必然最短。
走不下去（子指针为空）或走到单词末尾仍未遇到标记，说明无词根可用，原样返回。

解题步骤

建根节点，把每个词根逐字符插入：沿着字符下沉，缺失的子节点就新建。为什么用长度 26 的数组而不是哈希表：字符集固定为小写字母，数组寻址是无冲突的常数时间，比哈希表更快也更省心；代价是每个节点固定占 26 个指针，属于典型的空间换时间。

插入结束时在末端节点上写入 word = 词根。为什么存整个词根而不是只存一个布尔标记：查询命中时需要直接产出替换结果，存字符串省去了「沿路收集字符再拼接」的一步；若只存布尔值也可行，但要在查询时额外维护一个缓冲区。

把句子按空格切成单词数组。为什么先整体切分：题目要求按原顺序输出且分隔符固定为单空格，先切分再逐词处理，最后 join 回去，能保证分隔符不多不少。

对每个单词从根开始逐字符下沉：子指针为空则立刻返回原单词；否则下沉一层，并检查新节点是否带词根标记，带则立刻返回该词根。为什么「先下沉再检查」：根节点代表空前缀，它永远不该被当成词根命中；先检查会在根上误判。为什么命中就立即返回：深度自浅入深，第一次命中的词根长度最短，继续往下只会找到更长的词根，与题意相反。

单词字符耗尽仍未命中时返回原单词。为什么：说明该单词的任何前缀都不是词根，题目规定此时保持原样。

把处理后的单词用单空格拼接返回。

以 dictionary = ["cat", "bat", "rat"]、sentence = "the cattle was rattled by the battery" 走一遍。建树后有三条路径：c→a→t（末端标记 cat）、b→a→t（标记 bat）、r→a→t（标记 rat）。逐词处理：the 在根上找 t 的子指针，为空，原样保留。cattle 依次走 c、a、t，走完第三个字符时节点带标记 cat，立即返回 cat，后面的 tle 根本不用看。was 在根上找 w，为空，保留。rattled 走 r、a、t 命中 rat。by 走 b 成功下沉但该节点无标记，再找 y 的子指针为空，保留 by——注意这里下沉了一层却没有命中，正体现了「有路径不等于有词根」。the 同前保留。battery 走 b、a、t 命中 bat。拼接得到 the cat was rat by the bat。

代码实现

// 核心实现：Trie（前缀树），维护必要状态并避免重复处理。
class Solution {
    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word;
    }

    public String replaceWords(List<String> dictionary, String sentence) {
        TrieNode root = new TrieNode();
        for (String w : dictionary) {
            TrieNode node = root;
            for (char c : w.toCharArray()) {
                int idx = c - 'a';
                if (node.children[idx] == null) {
                    node.children[idx] = new TrieNode();
                }
                node = node.children[idx];
            }
            node.word = w;
        }

        String[] words = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < words.length; i++) {
            if (i > 0) {
                sb.append(' ');
            }
            sb.append(findRoot648(root, words[i]));
        }
        return sb.toString();
    }

    private String findRoot648(TrieNode root, String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                return word;
            }
            node = node.children[idx];
            if (node.word != null) {
                return node.word;
            }
        }
        return word;
    }
}

// 核心实现：Trie（前缀树），维护必要状态并避免重复处理。
type TrieNode struct {
    children [26]*TrieNode
    word     string
}

func replaceWords(dictionary []string, sentence string) string {
    root := &TrieNode{}
    for _, root1 := range dictionary {
        node := root
        for _, c := range root1 {
            idx := c - 'a'
            if node.children[idx] == nil {
                node.children[idx] = &TrieNode{}
            }
            node = node.children[idx]
        }
        node.word = root1
    }

    words := strings.Split(sentence, " ")
    for i, word := range words {
        node := root
        for _, c := range word {
            idx := c - 'a'
            if node.children[idx] == nil {
                break
            }
            node = node.children[idx]
            if node.word != "" {
                words[i] = node.word
                break
            }
        }
    }

    return strings.Join(words, " ")
}

复杂度分析

时间复杂度：$O(D + S)$，其中 $D$ 是词根表的总字符数、$S$ 是句子的总字符数。凭什么：建树阶段每个词根字符只被插入一次；查询阶段每个单词最多沿路径走它自身的长度，而所有单词长度之和不超过 $S$，每步都是一次 $O(1)$ 的数组寻址。

空间复杂度：$O(26D)$。凭什么：Trie 的节点数不超过词根总字符数 $D$，每个节点固定持有 26 个子指针；输出缓冲区额外占 $O(S)$，量级更小。

关键点总结

「前缀」二字就是 Trie 的触发词。凡是判定前缀、统计共同前缀、按前缀检索的题，先想 Trie；而「子串」要想后缀数组 / 后缀自动机，「相等」用哈希表就够，别混用。

Trie 的核心价值是把词表的公共前缀折叠成共享路径，把「查询代价 × 词表规模」降成「查询代价 × 1」。这条收益在词表越大、前缀越集中时越明显。

深度即长度这个性质让「最短匹配」变成「最早命中」：自浅入深遍历，第一次遇到终止标记就返回，天然拿到最短解。若题目改成要「最长匹配」，则要一路走到底并记录最后一次命中的位置。

节点上放什么标记决定了查询能返回什么。存布尔值只能回答「有没有」，存字符串能直接产出结果，存计数能支持词频统计，存求和值能支持前缀求和（如「键值映射」一题）。设计 Trie 时先想清楚要回答什么问题。

面试视角：手写 Trie 时先把 TrieNode 的字段定义讲清楚（26 个子指针 + 标记字段），再写 insert、再写 query，顺序清晰比一次写对更重要；被追问优化时可以提「字符集稀疏时改用哈希表存子节点」「词根表很小时直接用 HashSet 枚举前缀也能过」。

易错点总结

错误写法：在下沉之前就检查当前节点的词根标记；用例 dictionary = ["a"]、sentence = "b" → 在根节点上做检查，若根被误标记会把 b 替换掉；即便根未标记，这种写法在检查顺序上也会漏掉最后一个字符对应的节点。

错误写法：命中词根后不立即返回，继续走完整个单词并取最后一次命中；用例 dictionary = ["a", "aa"]、sentence = "aaa" → 返回 aa，正确答案是 a，因为题目要最短词根。

错误写法：子指针为空时用 continue 而不是返回原单词；用例 dictionary = ["cat"]、sentence = "cbat" → 走到 b 时断链却继续往下找，可能在后续字符上错误命中，或访问空指针崩溃。

错误写法：把「节点存在」当成「命中词根」；用例 dictionary = ["bat"]、sentence = "by" → 走完 b 后节点存在但没有词根标记，若据此返回会输出 b，正确答案是保留原词 by。

错误写法：字符转下标写成 c - 'A' 或忘记转下标直接用字符值索引；用例任意输入 → 下标变成 32 以上或负数，数组越界异常。

错误写法：Go 里用 node.word != "" 判定命中却把空字符串词根插入了树；用例词根表含空串 → 标记写成空字符串等同于未标记，命中判定失效。本题词根非空所以安全，但换成允许空串的场景就必须改用独立的布尔字段。

错误写法：用 sentence.split("\\s+") 或 strings.Fields 切分并用单空格拼接；用例句子首尾或中间存在多个空格 → 输出的空格数与输入不一致。本题保证单空格分隔，但一旦按「任意空白」切分就丢失了还原原格式的能力。

错误写法：把结果一路用 result += word + " " 拼接；用例句子含 $10^5$ 个单词 → Java 中字符串不可变导致每次拼接都复制全串，时间退化到 $O(S^2)$ 超时，必须用 StringBuilder 或数组 join。

错误写法：末尾多拼一个空格或漏掉单词间的空格；用例 sentence = "a b" → 输出 "a b " 或 "ab"，与期望字符串不等直接判错。

错误写法：对每个单词都重新建一次 Trie；用例句子含大量单词 → 建树是 $O(D)$，乘上单词数直接超时，Trie 必须在处理句子之前一次性建好。

相似题目

题目	难度	考察点
208. 实现 Trie (前缀树)	中等	从「用 Trie」变成「造 Trie」，要同时实现精确查找与前缀存在性判断
677. 键值映射	中等	节点上存的是数值并要沿路累加，还需处理同一 key 被覆盖时的差量更新
676. 实现一个魔法字典	中等	匹配允许恰好一处字符不同，查询要在树上带「已用修改次数」做搜索
720. 词典中最长的单词	中等	要求路径上每个前缀都必须是词典中的单词，查询变成对 Trie 的深度搜索