LeetCode LCR 063. 单词替换

2026-03-28 HGNULB 约 8 分钟

文章信息 5 个分类 5 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 063. 单词替换

题意分析

给一个词根表和一句由空格分隔的句子，句子中的每个单词，如果它能由词根表里的某个词根加上后缀构成，就把它替换成那个词根；如果能匹配多个词根，取最短的那个；匹配不上的单词原样保留。最后把处理后的单词重新用单个空格拼回一句话。

「取最短词根」这个要求决定了匹配方式：不能拿到一个能匹配的词根就随便用，而必须在所有能作为该单词前缀的词根里挑长度最小的。等价地说，从单词的第一个字符开始逐位加长前缀，第一次撞上词根表里的词，就是最短的那个，可以立刻停手。

「继承词」必须是单词的前缀，而不是任意子串。"cattle" 能被 "cat" 替换，但 "scatter" 不能——这条限制把问题从子串匹配收窄成前缀匹配，是可以用哈希直接查的关键。

约束给出的信号是：词根数与句子中的单词数都在 $10^3$ 量级，单个词根与单个单词的长度都不超过 100。长度上界很小，说明「对每个单词枚举它的所有前缀」这种 $O(L^2)$ 的做法完全够用，不需要为常数去上更复杂的结构。

边界上要注意：词根本身可能正好等于某个单词，此时替换成它自己，结果不变；某个词根可能是另一个词根的前缀，此时短的那个必须胜出；输出必须是单空格分隔，不能多出首尾空格。

解法：哈希表统计状态

核心思路

暴力做法是对句子中的每个单词，遍历整张词根表，逐个判断该词根是不是这个单词的前缀，把所有命中的词根收集起来再取最短。这需要 $O(N \cdot M \cdot L)$ 次字符比较，其中 $N$ 是单词数、$M$ 是词根数、$L$ 是长度上界。

瓶颈在于比较的方向搞反了：它拿着「不知道有没有用的词根」去试探单词，绝大多数词根连第一个字符都对不上，却仍然要付出一次调用开销；而且收集完所有命中再取最短，做了大量注定被丢弃的工作。

反过来观察：一个长度为 $L$ 的单词，它的前缀只有 $L$ 个，数量极少且完全确定。既然词根必须是单词的前缀，那么「这个单词能被哪些词根替换」等价于「它的这 $L$ 个前缀里哪些出现在词根表中」。方向一反，需要试探的候选就从 $M$ 个词根压缩到 $L$ 个前缀。

于是把词根表灌进一个哈希集合，查询单次 $O(L)$（哈希与比较的代价随串长）。对每个单词，从长度 1 的前缀开始逐位加长去查集合，第一次命中即返回——因为前缀是按长度递增枚举的，第一个命中的必然是最短的那个，这正好把「取最短」这个要求变成了「提前退出」而不是「收集后再挑」。

维持的不变量是：处理到长度 j 的前缀时，所有长度小于 j 的前缀都已确认不在词根表中。因此一旦命中就可以断言此刻的前缀是最短可行词根，直接写回并跳出内层循环；若 $L$ 个前缀全部落空，则这个单词没有任何词根可用，保持原样。

解题步骤

先把词根表整体倒进一个哈希集合。用集合而不是保持列表，是为了把「某个字符串是不是词根」从 $O(M)$ 的线性扫描降为一次哈希查询；同时天然去掉了词根表里的重复项。

按单个空格切分句子得到单词数组。题目保证单词之间恰好一个空格且无首尾空格，所以直接切分不会产生空串。

对每个单词，令前缀长度 j 从 1 递增到单词长度，逐个取出前缀去集合里查。从 1 开始而不是从 0 开始，是因为空串不是合法词根；上界取到单词长度本身，是因为词根可以正好等于整个单词。

一旦某个前缀命中，就地把数组中的这个单词覆盖成该前缀，并立即 break。break 是「取最短」的实现，去掉它就会一路查到最长的命中词根，语义完全反了。

整个内层循环跑完仍未命中，什么都不做，单词保持原值——这就是「无法替换则保留原词」。

最后用单个空格把数组重新拼接成字符串返回。原地覆盖数组再统一拼接，避免了逐个追加时对首尾空格的特判。

以 dictionary = ["cat", "bat", "rat"]、sentence = "the cattle was rattled by the battery" 走一遍：集合里是 cat、bat、rat，句子切成七个单词。处理 "the"：前缀 t、th、the 都不在集合中，保持 "the"。处理 "cattle"：前缀 c 落空、ca 落空、cat 命中，立即把它改成 "cat" 并跳出，后面的 catt、cattl、cattle 根本不去查。处理 "was"：w、wa、was 全部落空，保留。处理 "rattled"：r、ra 落空，rat 命中，改成 "rat" 后跳出。处理 "by"：两个前缀都落空，保留。处理 "the"：同前，保留。处理 "battery"：b、ba 落空，bat 命中，改成 "bat"。数组变成 ["the", "cat", "was", "rat", "by", "the", "bat"]，用空格拼回，返回 "the cat was rat by the bat"。

代码实现

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        Set<String> s = new HashSet<>(dictionary);
        String[] words = sentence.split(" ");
        for (int i = 0; i < words.length; ++i) {
            String word = words[i];
            for (int j = 1; j <= word.length(); ++j) {
                String t = word.substring(0, j);
                if (s.contains(t)) {
                    words[i] = t;
                    break;
                }
            }
        }
        return String.join(" ", words);
    }
}

func replaceWords(dictionary []string, sentence string) string {
    s := map[string]bool{}
    for _, v := range dictionary {
        s[v] = true
    }
    words := strings.Split(sentence, " ")
    for i, word := range words {
        for j := 1; j <= len(word); j++ {
            t := word[:j]
            if s[t] {
                words[i] = t
                break
            }
        }
    }
    return strings.Join(words, " ")
}

复杂度分析

时间复杂度：$O(D + N \cdot L^2)$，$D$ 是词根表的总字符数（建集合），$N$ 是单词数，$L$ 是单词长度上界。每个单词最多枚举 $L$ 个前缀，取子串与哈希各需 $O(L)$，故单词内是 $O(L^2)$。在 $L \le 100$ 的约束下总量很小。

空间复杂度：$O(D + S)$，$D$ 来自哈希集合中存下的全部词根，$S$ 是切分后单词数组与最终拼接结果占用的空间。

关键点总结

匹配方向的选择是这题的分水岭：「用词根试探单词」的候选是 $M$ 个，「用单词的前缀去查词根」的候选只有 $L$ 个。当一侧的候选集合天然更小且完全枚举得起时，就该把它当作查询键。

「取最短」通过「按长度递增枚举 + 首次命中即退出」来实现，比「全部收集再排序取最小」更省也更不容易写错，是一条可迁移的贪心退出原则。

前缀匹配与子串匹配是两回事。看到「继承词加后缀构成派生词」要立刻确认锚点在开头，否则会误用更重的子串匹配工具。

原地覆盖单词数组、最后统一 join，可以彻底避开手工拼接时的首尾空格问题，是字符串重组题的稳妥写法。

面试视角：先给哈希前缀枚举的解法拿到正确性，再主动提一句「若词根数量极大或需要在线查询，可换成 Trie，把单词的匹配代价从 $O(L^2)$ 降到 $O(L)$」，展示出你知道边界在哪，而不是只会一种工具。

面试视角：常见追问是「如果词根有几百万条怎么办」。此时哈希集合的内存与取子串的开销都成问题，答 Trie：公共前缀共享节点省内存，沿字符下沉时遇到词根终点标记立刻返回，天然就是最短匹配。

易错点总结

错误写法：命中后不 break，继续枚举更长的前缀。用例 dictionary = ["a", "aa", "aaa"]、sentence = "aaaa" → 一路匹配到 "aaa" 才停，输出 "aaa"，正确答案是最短的 "a"。

错误写法：前缀长度从 0 开始枚举。用例任意句子 → 空串若被误判在集合中会把所有单词替换成空串；即便集合里没有空串，也白白多做一轮查询并可能拼出多余空格。

错误写法：前缀长度上界写成 j < word.length()。用例 dictionary = ["cat"]、sentence = "cat" → 只枚举到 "ca" 就结束，词根等于整词的情况被漏掉，输出 "cat" 虽然凑巧相同，但换成 dictionary = ["cats"]、sentence = "cats" 时逻辑已错，应替换却判定为未命中。

错误写法：把「词根是单词的前缀」写成 word.contains(root) 的子串判断。用例 dictionary = ["cat"]、sentence = "scatter" → 判定命中并替换成 "cat"，正确答案是保留 "scatter"。

错误写法：方向写反，判断成 root.startsWith(word)。用例 dictionary = ["cattle"]、sentence = "cat" → 判定命中，把 "cat" 换成更长的 "cattle"，正确答案是保留 "cat"。

错误写法：未命中的单词被丢弃或替换成空串。用例 dictionary = ["cat"]、sentence = "the cattle" → 输出 " cat" 或 "cat"，正确答案是 "the cat"，无法替换的单词必须原样保留。

错误写法：拼接时逐个追加单词和空格，不处理末尾。用例 dictionary = []、sentence = "a b" → 输出 "a b " 末尾多一个空格，与期望字符串不等。

错误写法：用 split("\\s+") 或先 trim 再切分，试图「稳妥」处理空白。用例句子本身合法时 → 行为一致，但一旦题目数据含有意为之的连续空格结构，切分结果与原句的单词数不再一致，重组后的句子与预期不符；按题目保证的单空格直接切分才是与输入契约一致的写法。

相似题目

题目	难度	考察点
648. 单词替换	中等	与本题同题，适合对照哈希前缀枚举与 Trie 下沉两种实现
208. 实现 Trie (前缀树)	中等	把本题的前缀查询固化成可复用的数据结构，需区分前缀与整词
211. 添加与搜索单词 - 数据结构设计	中等	查询串带通配符，无法再用哈希整串命中，必须走树上分支
720. 词典中最长的单词	中等	目标从最短前缀变成最长且逐字符可达的词，判定条件沿路径累积
1268. 搜索推荐系统	中等	每个前缀要返回多个候选而非一个词根，需在节点上维护结果集
139. 单词拆分	中等	词典匹配从「替换单个前缀」升级为「整串能否被完全切分」
140. 单词拆分 II	困难	要枚举全部切分方案，需在词典命中的基础上做回溯与记忆化