LeetCode LCR 062. 实现 Trie (前缀树)

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

题目描述

✅ LCR 062. 实现 Trie (前缀树)

image-20260929010501215

image-20260929010501216

题意分析

实现一个保存单词的前缀树，支持插入、查询完整单词、查询前缀三种操作。完整单词查询要求这个字符串曾作为一个整体插入过；前缀查询只要求某个已插入单词以它开头。

输入只有小写英文字母，因此每个节点最多有 $26$ 种向下的字符转移。重复插入同一个单词不应改变查询结果，查询串也可能在中途就没有对应路径。

解法：前缀树与单词终止标记

核心思路

[!blue]

将一个单词的字符依次看成从根出发的边，根表示空前缀，走过前 k 个字符后所在的节点就表示这个长度为 k 的前缀。具有公共开头的单词共享同一段路径，因此查询前缀时可以直接沿字符走，不必逐个检查所有单词。

每个节点保存 children[26] 和 isEnd：children[c - 'a'] 指向追加字符 c 后的前缀节点；isEnd 表示当前路径是否曾作为完整单词插入。结束节点不一定是叶子，因为一个完整单词也可能是另一个更长单词的前缀。

插入时从根开始，遇到不存在的子节点才创建，然后沿该节点继续。走完整个单词后，只把最后一个节点的 isEnd 置为真。已有路径会被复用，原有分支和结束标记不受影响，所以更长、较短以及重复单词都能正确插入。

两种查询先执行相同的寻路过程：处理完前 k 个字符时，当前节点恰好对应这 k 个字符；若下一条边不存在，就说明没有已插入单词经过这个前缀，可以立即失败。全部字符走完后，searchPrefix 返回终点节点。

startsWith 只检查终点是否存在；search 还检查终点的 isEnd。路径存在保证某个已插入单词拥有这个前缀，结束标记则进一步保证查询串本身被完整插入过。只有一个空根时，任何题目允许的非空查询都会因缺少路径而失败。

解题步骤

  1. 构造根节点，初始化 $26$ 个空子节点引用，结束标记为假。
  2. 插入单词时逐字符定位子节点，缺失则创建，最后只标记完整单词的终点。
  3. 公共寻路函数沿查询串前进，遇到缺失边返回空，走完则返回终点。
  4. 前缀查询判断终点非空；完整单词查询判断终点非空且 isEnd 为真。

代码实现

class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
    }

    public void insert(String word) {
        Trie node = this;

        for (char c : word.toCharArray()) {
            int idx = c - 'a';

            if (node.children[idx] == null) {
                node.children[idx] = new Trie();
            }

            node = node.children[idx];
        }

        node.isEnd = true;
    }

    public boolean search(String word) {
        Trie node = searchPrefix(word);

        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        Trie node = searchPrefix(prefix);

        return node != null;
    }

    private Trie searchPrefix(String s) {
        Trie node = this;

        for (char c : s.toCharArray()) {
            int idx = c - 'a';

            if (node.children[idx] == null) {
                return null;
            }

            node = node.children[idx];
        }

        return node;
    }
}

type Trie struct {
    children [26]*Trie
    isEnd    bool
}

func Constructor() Trie {
    return Trie{}
}

func (this *Trie) Insert(word string) {
    node := this
    for _, c := range word {
        idx := c - 'a'
        if node.children[idx] == nil {
            node.children[idx] = &Trie{}
        }
        node = node.children[idx]
    }
    node.isEnd = true
}

func (this *Trie) Search(word string) bool {
    node := this.SearchPrefix(word)
    return node != nil && node.isEnd
}

func (this *Trie) StartsWith(prefix string) bool {
    node := this.SearchPrefix(prefix)
    return node != nil
}

func (this *Trie) SearchPrefix(s string) *Trie {
    node := this
    for _, c := range s {
        idx := c - 'a'
        if node.children[idx] == nil {
            return nil
        }
        node = node.children[idx]
    }
    return node
}

复杂度分析

  • 时间复杂度：每次插入或查询为 $O(L)$，L 为本次字符串长度；每个字符只进行固定大小数组中的一次寻址。
  • 空间复杂度：持久空间为 $O(26C)$，C 为包含根在内的节点数，至多为插入字符总数加一。公共前缀共用节点；Java 的 toCharArray() 还会在单次操作中产生 $O(L)$ 临时数组，Go 的字符遍历只需常数额外空间。

关键点总结

[!green]

  • 路径回答“前缀是否存在”，isEnd 回答“该前缀是否也是完整单词”。
  • 结束节点可以继续拥有子节点，不能用是否为叶子代替单词结束标记。
  • 插入复用已有节点，只补缺失分支；重复插入只会再次将相同终点标为真。

易错点总结

[!yellow]

  • search 只检查路径而不检查 isEnd，会把从未单独插入的前缀误当成完整单词。
  • 插入时把沿途所有节点都标成结束，会错误增加一批短单词。
  • 覆盖已存在的孩子节点，会丢失其他单词共享的后续分支。
  • 前缀查询不要求 isEnd，否则会漏掉仅作为更长单词开头的前缀。

相似题目

题目 难度 关联与区别
211. 添加与搜索单词 - 数据结构设计 中等 在Trie基础上增加通配符搜索，遇到点号需要探索多个孩子。
677. 键值映射 中等 在Trie的前缀路径上增加数值聚合，终点不再只表示单词存在。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/16385184
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！