LeetCode LCR 063. 单词替换

Categories:

题目描述
思路分析
1. 解法一：Trie 前缀树（推荐）
相似题目

题目描述

✅ LCR 063. 单词替换

思路分析

解法一：Trie 前缀树（推荐）

核心思路：

将词根集合构建成 Trie，并用 isEnd 标记词根结束。

对句子中的每个单词，从 Trie 根开始走，遇到 isEnd 即返回最短词根。

若无法匹配到词根，保留原单词。

复杂度分析：

时间复杂度：O(total)，其中 total 表示字典与句子总字符数。

空间复杂度：O(total)，Trie 需要存储所有词根字符。

import java.util.*;

class Solution {
    private static class TrieNode {
        TrieNode[] next = new TrieNode[26];
        boolean isEnd;
    }

    public String replaceWords(List<String> dictionary, String sentence) {
        TrieNode root = new TrieNode();
        for (String word : dictionary) {
            insert(root, word);
        }

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

    private void insert(TrieNode root, String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (cur.next[idx] == null) {
                cur.next[idx] = new TrieNode();
            }
            cur = cur.next[idx];
        }
        cur.isEnd = true;
    }

    private String replace(TrieNode root, String word) {
        TrieNode cur = root;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (cur.next[idx] == null) {
                return word;
            }
            sb.append(word.charAt(i));
            cur = cur.next[idx];
            if (cur.isEnd) {
                return sb.toString();
            }
        }
        return word;
    }
}

import "strings"

type TrieNode struct {
    next  [26]*TrieNode
    isEnd bool
}

func replaceWords(dictionary []string, sentence string) string {
    root := &TrieNode{}
    for _, word := range dictionary {
        insertTrie(root, word)
    }

    parts := strings.Split(sentence, " ")
    for i := range parts {
        parts[i] = replaceWord(root, parts[i])
    }
    return strings.Join(parts, " ")
}

func insertTrie(root *TrieNode, word string) {
    cur := root
    for i := 0; i < len(word); i++ {
        idx := word[i] - 'a'
        if cur.next[idx] == nil {
            cur.next[idx] = &TrieNode{}
        }
        cur = cur.next[idx]
    }
    cur.isEnd = true
}

func replaceWord(root *TrieNode, word string) string {
    cur := root
    for i := 0; i < len(word); i++ {
        idx := word[i] - 'a'
        if cur.next[idx] == nil {
            return word
        }
        cur = cur.next[idx]
        if cur.isEnd {
            return word[:i+1]
        }
    }
    return word
}

相似题目

题目	难度	考察点
208. 实现 Trie (前缀树)	中等	Trie
212. 单词搜索 II	困难	Trie
14. 最长公共前缀	简单	字符串
677. 键值映射	中等	Trie
820. 单词的压缩编码	中等	反向 Trie

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/48550215