LeetCode 208. 实现 Trie (前缀树)

约 6 分钟
文章信息 19 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 20-50 LeetCode 75 LeetCode 热题 100 面试经典 150 题 腾讯 字节 阿里 华为 微软 美团 拼多多 百度 快手 虾皮 猿辅导
标签
字符串 哈希表 设计 字典树

题目描述

✅ 208. 实现 Trie (前缀树)

image-20260928204028315

image-20260928204028317

题意分析

实现一个前缀树，支持插入单词、判断完整单词是否已经插入，以及判断是否存在以给定字符串开头的已插入单词。输入只包含小写英文字母。

完整单词查找和前缀查找的要求不同：一段字符虽然出现在某个已插入单词的开头，但它自身不一定曾被作为单词插入。重复插入不需要增加计数，本题只关心是否存在。

解法：数组孩子节点实现 Trie

核心思路

[!blue]

Trie 把公共前缀保存为公共路径。根表示空前缀，从根沿某个字母对应的孩子走一步，就在前缀末尾增加这个字母。只要两个单词的开头相同，它们就复用相同的前几段路径，直到不同字符才分叉。

每个节点保存 26 个孩子引用，用 字符 - 'a' 直接定位下一步。还要单独保存布尔标记 isEnd，表示从根到这里的路径是否恰好对应一个完整插入过的单词。某个节点即使还有孩子，也可能是较短单词的结束位置，所以不能用叶子节点代替结束标记。

插入从根开始逐字符走，孩子存在就复用，不存在才创建。处理完整个单词后，只将最终节点标记为结束；原有孩子和其他终点标记都保持，因此继续插入更短或更长的单词不会破坏已有内容。

两种查询共用只读路径查找 searchPrefix。如果中途缺少孩子，说明整段字符无法作为任何已有单词的前缀，查询失败。路径全部存在时，startsWith 已经满足要求；search 还必须检查终点的 isEnd，确认不是仅仅走到了某个长单词中间。

只有插入可以创建节点。查询失败时直接返回，才能保证一次不存在的查询不会凭空改变后续前缀查询的结果。

解题步骤

  1. 创建根节点；每个节点包含全空的孩子数组和默认值为假的 isEnd。
  2. 插入时从根逐字符前进，对缺失孩子创建新节点，处理完最后一个字符后设置 isEnd = true。
  3. 路径查询也从根逐字符前进，但只读取已有孩子，遇到空引用立即返回失败。
  4. search 要求整条路径存在且最后节点是单词终点。
  5. startsWith 只要求整条路径存在，不检查是否已经到达某个单词的结尾。

代码实现

class Trie {
    private final TrieNode root = new TrieNode();

    public Trie() {}

    public void insert(String word) {
        TrieNode node = root;

        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';

            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }

            node = node.children[index];
        }

        // 路径存在只代表前缀，完整单词还需在终点单独标记。
        node.isEnd = true;
    }

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

        // 查询完整单词必须同时满足路径存在与单词结束。
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private TrieNode searchPrefix(String text) {
        TrieNode node = root;

        for (int i = 0; i < text.length(); i++) {
            node = node.children[text.charAt(i) - 'a'];

            if (node == null) {
                return null;
            }
        }

        return node;
    }

    private static class TrieNode {
        private final TrieNode[] children = new TrieNode[26];
        private boolean isEnd;
    }
}

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

func Constructor() Trie {
    return Trie{}
}

func (this *Trie) Insert(word string) {
    node := this
    for i := 0; i < len(word); i++ {
        index := word[i] - 'a'
        if node.children[index] == nil {
            node.children[index] = &Trie{}
        }
        node = node.children[index]
    }
    // 路径存在只代表前缀，完整单词还需在终点单独标记。
    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 {
    return this.searchPrefix(prefix) != nil
}

func (this *Trie) searchPrefix(text string) *Trie {
    node := this
    for i := 0; i < len(text); i++ {
        node = node.children[text[i]-'a']
        if node == nil {
            return nil
        }
    }
    return node
}

复杂度分析

  • 时间复杂度：三种操作均为 $O(L)$，其中 $L$ 是本次传入字符串的长度；每个字符只做一次数组寻址。
  • 空间复杂度：$O(T)$，其中 $T$ 是所有插入过程中实际创建的节点数，最坏为所有单词长度之和。每个节点的 26 个孩子槽位是固定常数。

关键点总结

[!green]

  • 从根到节点的路径表示前缀，公共前缀对应的节点被多个单词共享。
  • 路径存在表示可作为前缀，结束标记表示曾作为完整单词插入，两种信息缺一不可。
  • 插入负责补节点，查询负责读路径；重复插入只会再次设置结束标记，不产生额外副作用。

易错点总结

[!yellow]

  • 完整单词查询只检查路径存在，会把未单独插入的较短前缀也当成完整单词。
  • 前缀查询额外要求 isEnd，会漏掉停在长单词中间的合法前缀。
  • 插入时没有标记最终节点，后续完整单词查询就无法确认插入是否结束。
  • 用“没有孩子”代表单词终点，无法同时保存某个单词和以它为前缀的更长单词。
  • 查询时顺手创建缺失孩子，会改变数据结构，让本来不存在的前缀在后续查询中出现。
  • 复用前缀时替换已有节点，会丢掉其下保存的其他单词，应只在孩子不存在时创建。

相似题目

题目 难度 关联与区别
211. 添加与搜索单词 - 数据结构设计 中等 在Trie基础上增加通配符搜索，遇到点号需要探索多个孩子。
677. 键值映射 中等 在Trie的前缀路径上增加数值聚合，终点不再只表示单词存在。
212. 单词搜索 II 困难 用字典树共享字符串前缀；本题支持插入、完整词查询和前缀查询，该题把字典树与网格回溯结合。
648. 单词替换 中等 用字典树共享字符串前缀；本题支持插入、完整词查询和前缀查询，该题沿词前缀找到最短词根。
补充题 152. 支持删除和词频统计的字典树 中等 沿用字典树逐字符走节点的查找；补充题还维护词频和删除后的计数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/63927217
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！