LeetCode LCR 063. 单词替换

约 5 分钟
文章信息 5 个分类 5 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 字符串 哈希表 LCR 字典树

题目描述

✅ LCR 063. 单词替换

image-20260929010513358

image-20260929010513359

题意分析

用词典中的词根替换句子里的单词：词根必须是该单词的前缀，若有多个匹配词根，就选择长度最短的一个；没有匹配词根时保留原单词。

题目保证单词之间只有一个空格，且句子没有首尾空格，因此可以按单空格拆分、分别处理，再按同样的分隔方式连接。词根最长为 $100$，句中单词最长为 $1000$，两种长度上限不能混用。

解法：从短到长枚举词根前缀

核心思路

[!blue]

一个能替换当前单词的词根，必然等于它的某个前缀。与其为每个单词遍历整个词典，可以先把词根放入集合 s，再枚举这个单词可能匹配的前缀，直接判断它是否属于词典。

设词典中最长词根长度为 maxRoot。长度超过 maxRoot 的前缀不可能是词根，长度超过单词自身也没有意义，所以只需检查长度 $1$ 到 min(word.length, maxRoot)。

前缀按长度递增枚举。第一次命中时，所有更短的前缀都已经确认不是词根，因此当前命中的就是最短词根；立即替换并退出，后面即使还有更长的匹配也不应采用。若全部候选都失败，这个单词不存在匹配词根，保持原值即可。

每个单词的替换只由它自身与固定词典决定，不会影响其他单词的匹配。因此可以依次更新 words 中的对应位置，最后用单空格连接。词根等于整个单词时也属于合法前缀，替换后的内容只是与原词相同。

解题步骤

  1. 建立词根集合 s，扫描词典得到最长词根长度 maxRoot。
  2. 按单空格拆分句子，逐个读取原单词 word。
  3. 令前缀长度从 $1$ 增长到单词长度与 maxRoot 的较小值，查询此前缀是否在集合中。
  4. 首次命中就写回该前缀并结束当前单词的循环；没有命中则保留原词。
  5. 用单空格连接结果并返回。

代码实现

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        Set<String> s = new HashSet<>(dictionary);
        int maxRoot = 0;

        for (String root : dictionary) {
            maxRoot = Math.max(maxRoot, root.length());
        }

        String[] words = sentence.split(" ");

        for (int i = 0; i < words.length; ++i) {
            String word = words[i];

            for (int j = 1; j <= word.length() && j <= maxRoot; ++j) {
                String t = word.substring(0, j);

                if (s.contains(t)) {
                    words[i] = t;
                    break;
                }
            }
        }

        return String.join(" ", words);
    }
}

import (
    "strings"
)

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

复杂度分析

  • 时间复杂度：设词根总字符数为 D、句子长度为 S、单词数为 N，第 i 个单词长度为 L_i，最多检查的前缀长度为 $B_i=\min(L_i,R)$，其中 R 是最长词根长度。期望时间为 $O(D+S+\sum B_i^2)$，也可上界为 $O(D+S+NR^2)$。长度为 j 的前缀需要按其字符计算哈希，Java 还会复制子串，不能把每次前缀查询都视为不计字符长度的常数操作。
  • 空间复杂度：$O(D+S)$ 的上界，用于词根集合、分词结果和返回字符串。

关键点总结

[!green]

  • 所有合法词根都在单词前缀中，集合查询只需判断成员是否存在。
  • 递增长度的第一次命中就是最短匹配，必须立即停止。
  • maxRoot 限制候选长度，避免为长单词生成不可能命中的更长前缀。

易错点总结

[!yellow]

  • 从长前缀开始或命中后继续覆盖，会违背最短词根要求。
  • 查找任意子串不能代替前缀匹配，词根必须从单词首字符开始。
  • 候选长度应允许等于整个单词长度，词根与单词相同也合法。
  • 未命中的单词要原样保留，不能丢弃或替换为空串。

相似题目

题目 难度 关联与区别
208. 实现 Trie (前缀树) 中等 复用Trie前缀查找，本题遇到第一个词根终点立即停止，以保留最短词根。
720. 词典中最长的单词 中等 同样利用前缀终点标记，原题要求构建单词的每一级前缀都存在，本题只需最短匹配词根。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/48550215
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！