208. 实现Trie(前缀树)#

你有没有好奇过，当你在搜索框输入时，为什么能瞬间给出相关的搜索建议？今天，让我们揭开这个神奇功能背后的数据结构：Trie（前缀树）。

🌟 生活中的前缀树#

想象你在整理一本英语词典：

所有以’a’开头的词放在A章节
在A章节中，再按第二个字母分类
以此类推…

这种层层递进的组织方式，就是前缀树的思想！

问题描述#

题目目标#

请你实现 Trie（前缀树）类，支持以下操作：insert(String word) 插入字符串，search(String word) 判断字符串是否在前缀树中，startsWith(String prefix) 判断是否存在以给定前缀开头的字符串。

示例 1#

输入：

["Trie","insert","search","search","startsWith","insert","search"]
[[],["apple"],["apple"],["app"],["app"],["app"],["app"]]

text

输出： [null,null,true,false,true,null,true] 操作示意：

Trie()
insert('apple')
search('apple') -> True
search('app') -> False
startsWith('app') -> True
insert('app')
search('app') -> True

text

说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

补充说明#

示例中的输入输出采用“操作序列 + 参数列表”的形式，表示依次调用对象方法。

💡 前缀树是什么？#

Trie（读作”try”或”tree”）是一种树形数据结构：

每个节点代表一个字符
从根节点到某个节点的路径表示一个字符串
特别适合用来存储和查找字符串集合

🎨 可视化理解#

假设我们要存储这些单词：{“cat”, “car”, “card”}

plaintext

看到了吗？这就像一个字符串的”家谱树”！

⚡ 完整代码实现#

class Trie {
    // TrieNode：前缀树中的单个节点，表示一个字符位置
    private class TrieNode {
        // children[i]：指向字符 ('a' + i) 对应的下一个节点
        private TrieNode[] children;
        // isEnd：标记“从根到当前节点”这条路径是否构成一个完整单词
        private boolean isEnd;

        public TrieNode() {
            // 初始化 26 个英文字母槽位（仅处理小写字母 a~z）
            children = new TrieNode[26];
            // 新节点默认不是某个单词的结尾
            isEnd = false;
        }
    }

    // root：前缀树根节点，不存具体字符，只作为所有单词的起点
    private TrieNode root;

    public Trie() {
        // 构造函数：创建空 Trie 时，先初始化根节点
        root = new TrieNode();
    }

    // 插入一个完整单词到前缀树
    public void insert(String word) {
        // node：用于沿着单词路径逐字符向下移动
        TrieNode node = root;
        // 依次处理单词中的每个字符
        for (char c : word.toCharArray()) {
            // 把字符映射到数组下标：'a'->0, 'b'->1, ..., 'z'->25
            int index = c - 'a';
            // 如果该字符对应的子节点不存在，说明这条路径还没建立，需要新建节点
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            // 沿着该字符路径继续向下
            node = node.children[index];
        }
        // 循环结束后，node 落在单词最后一个字符节点上，将其标记为单词结尾
        node.isEnd = true;
    }

    // 查找某个单词是否“完整存在”于 Trie 中
    public boolean search(String word) {
        // 先按前缀查找，拿到单词最后一个字符对应的节点
        TrieNode node = searchPrefix(word);
        // 只有两者都满足才返回 true：
        // 1) 路径存在（node != null）
        // 2) 该路径正好是一个完整单词结尾（node.isEnd == true）
        return node != null && node.isEnd;
    }

    // 判断是否存在以 prefix 作为前缀的单词
    public boolean startsWith(String prefix) {
        // 前缀判断只需要路径存在，不要求是单词结尾
        return searchPrefix(prefix) != null;
    }

    // 公共查找方法：沿着给定字符串路径向下走，返回最终节点；若中途断开则返回 null
    private TrieNode searchPrefix(String prefix) {
        // 从根节点开始匹配
        TrieNode node = root;
        // 逐字符检查路径是否存在
        for (char c : prefix.toCharArray()) {
            // 将字符映射到 children 下标
            int index = c - 'a';
            // 若当前字符路径不存在，说明前缀/单词不存在，直接返回 null
            if (node.children[index] == null) {
                return null;
            }
            // 路径存在，继续向下一层
            node = node.children[index];
        }
        // 所有字符都匹配成功，返回匹配终点节点
        return node;
    }
}

java

🎬 模拟运行过程#

让我们一步步看看如何构建一个前缀树：

1. 初始状态：
   root

2. 插入"cat"：
   root
    |
    c
    |
    a
    |
    t*   (* 表示单词结尾)

3. 插入"car"：
   root
    |
    c
    |
    a
   / \
  t*  r*

4. 再插入"card"：
   root
    |
    c
    |
    a
   / \
  t*  r*
      |
      d*

plaintext

🔍 核心操作解析#

1. 插入操作#

就像在建立一个文件目录：

沿着已有的路径走
如果没路了，就新建路径
最后标记一下这是个完整的词

2. 查找操作#

像是在玩寻宝游戏：

顺着路径一直走
中途断了就返回false
找到了还要检查是否是完整的词

3. 前缀查找#

和普通查找类似，但更宽松：

不需要走到尽头
只要能找到这段路径就行

📊 复杂度分析#

时间复杂度：

插入：O(m)，m是单词长度
查找：O(m)
前缀查找：O(m)

空间复杂度：

O(TOTAL)，TOTAL是所有单词字符数的总和

🎯 实战应用场景#

搜索引擎的自动补全
拼写检查器
IP地址路由表
文件系统的路径管理

💡 性能优化技巧#

压缩前缀树：合并单一路径的节点

优化前：      优化后：
  c            ca
  |     →      |
  a            t
  |
  t

plaintext

使用HashMap代替数组：

private Map<Character, TrieNode> children;  // 更灵活，支持更多字符

java

🎁 思考题#

如何修改代码实现以下功能：

统计某个前缀出现的次数？
支持删除操作？
查找最长公共前缀？

如果你知道答案，或者有自己的想法？欢迎在评论区留言、讨论～

📝 代码模板总结#

实现Trie时的核心要点：

定义节点结构（children数组 + 结束标记）
实现三个基本操作（插入、查找、前缀查找）
抽取公共查找逻辑
注意字符索引转换