LeetCode 648. 单词替换

约 6 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 美团
标签
数组 字符串 哈希表 字典树

题目描述

✅ 648. 单词替换

image-20260929104431824

image-20260929104432001

题意分析

逐个处理句子中的单词：若字典中有词根是它的前缀，就替换成最短的那个词根；没有则保留原词。各单词的顺序保持不变，匹配必须从单词开头开始。

解法：Trie（前缀树）

核心思路

[!blue]
用字典树共享词根前缀，再沿单词找到第一个完整词根。 从树根出发的一条路径表示一个前缀，26 个孩子分别对应小写字母。插入词根时逐字符创建缺少的节点，并只在最后的节点保存完整词根 word；中间路径节点本身不代表字典中的词根。

查询单词时，从它的第一个字符开始沿同一条路径下降。每走一步，当前节点就表示已经读到的单词前缀，深度也就是前缀长度。第一次遇到保存了完整词根的节点时，所有更短前缀都已检查过而未命中，更长词根只可能在更深处，所以这个词根一定最短，可以立即停止。

若下一条分支不存在，就不可能再有词根沿当前单词前缀继续匹配；此前若有更短词根也早已返回，因此保留原词。若读完单词仍未遇到词根终点，同样保留原词。词根恰好等于整个单词时，在最后一个字符处就能正常命中。

字典树只构建一次，所有单词独立查询并按原顺序输出。题目保证单词之间只有一个空格，且没有前导、尾随空格，所以按单空格切分后再用单空格连接，正好恢复所需句子格式。

解题步骤

  1. 将所有词根插入字典树。
  2. 按原顺序逐个处理句子单词。
  3. 从树根向下查询，第一个终点即替换结果。
  4. 使用单个空格重新拼接。

代码实现

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;
    }
}

import "strings"

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 为句子总字符数。
  • 空间复杂度：$O(D+S)$，包含字典树、分词及输出缓冲。

关键点总结

[!green]

  • 深度就是词根长度，第一个终点保证最短。
  • 缺失分支意味着当前词无法沿此前前缀继续匹配。
  • 共享字典树只构建一次。
  • 词根非空，Java 的 word != null 和 Go 的 word != "" 都能区分完整词根与普通路径节点。

易错点总结

[!yellow]

  • 将普通路径节点当作完整词根：可能返回字典中没有的前缀。
  • 命中后继续取更长词根：违反最短要求。
  • 断链后跳过当前字符继续查：把前缀匹配变成子序列匹配。
  • 遗漏或多加输出空格：改变句子格式。

相似题目

题目 难度 关联与区别
208. 实现 Trie (前缀树) 中等 复用Trie前缀查找，本题遇到第一个词根终点立即停止，以保留最短词根。
720. 词典中最长的单词 中等 同样利用前缀终点标记，原题要求构建单词的每一级前缀都存在，本题只需最短匹配词根。
211. 添加与搜索单词 - 数据结构设计 中等 用字典树共享字符串前缀；本题沿词前缀找到最短词根，该题通配符查询时分支搜索。
212. 单词搜索 II 困难 用字典树共享字符串前缀；本题沿词前缀找到最短词根，该题把字典树与网格回溯结合。
677. 键值映射 中等 用字典树共享字符串前缀；本题沿词前缀找到最短词根，该题在前缀节点累计键值总和。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/24608248
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！