LeetCode 208. 实现 Trie（前缀树）

题目描述

Trie（发音类似 “try”）也叫前缀树或字典树，是一种专门用来高效处理字符串前缀问题的数据结构。

请你实现 Trie 类：

Trie() 初始化前缀树对象
void insert(String word) 向前缀树中插入字符串 word
boolean search(String word) 如果字符串 word 在前缀树中，返回 true
boolean startsWith(String prefix) 如果之前已经插入的字符串中存在前缀为 prefix 的单词，返回 true

题目本质

这道题并不是考某种复杂算法，而是考你是否理解 Trie 这种数据结构是怎么设计的。

它最核心的用途就是：

快速插入字符串
快速查找某个完整单词是否存在
快速判断某个前缀是否存在

如果用普通的字符串数组或 HashSet：

查完整单词可以很快
但查“前缀是否存在”就不够自然

而 Trie 天生就是为“公共前缀”设计的。

什么是 Trie

我们先看几个单词：

apple
app
ape

如果把它们存进 Trie 中，会发现：

a 是公共前缀
ap 也是公共前缀
它们在前两层是共享节点的

也就是说，Trie 会把字符串按字符一层一层存下来。

比如插入 apple：

root
 └── a
      └── p
           └── p
                └── l
                     └── e

如果再插入 app，其实只需要把已经存在的路径继续走到第二个 p，然后标记这里是一个完整单词的结尾即可。

所以 Trie 的优势就在于：

相同前缀只存一次。

这份代码的整体结构

class Trie {
    private static class Node {
        Node[] son = new Node[26];
        boolean end = false;
    }

    private final Node root = new Node();

    public void insert(String word) {
        Node cur = root;
        for (char c : word.toCharArray()) {
            c -= 'a';
            if (cur.son[c] == null) {
                cur.son[c] = new Node(); 
            }
            cur = cur.son[c];
        }
        cur.end = true;
    }

    public boolean search(String word) {
        return find(word) == 2;
    }

    public boolean startsWith(String prefix) {
        return find(prefix) != 0;
    }

    private int find(String word) {
        Node cur = root;
        for (char c : word.toCharArray()) {
            c -= 'a';
            if (cur.son[c] == null) {
                return 0;
            }
            cur = cur.son[c];
        }
        return cur.end ? 2 : 1;
    }
}

这份实现很简洁，思路也非常清楚。

它的关键点有两个：

每个节点维护一个长度为 26 的子节点数组
每个节点额外用一个 end 标记，表示这里是不是某个单词的结尾

节点结构为什么这样设计

1. `Node[] son = new Node[26]`

Node[] son = new Node[26];

这里表示：

每个节点最多有 26 个孩子
分别对应 'a' 到 'z'

比如：

'a' - 'a' = 0
'b' - 'a' = 1
'c' - 'a' = 2

这样就可以把字符直接映射到数组下标上，查找和插入都很快。

2. `boolean end = false`

boolean end = false;

这个标记非常关键。

因为有时候一个字符串既可能是完整单词，也可能只是另一个更长单词的前缀。

比如插入：

app
apple

那么：

走到 app 这个节点时，应该标记它是一个单词结尾
但它下面还可以继续接 l、e

所以必须用 end 单独记录：

当前节点是否对应一个完整单词的结束。

为什么需要 root 节点

private final Node root = new Node();

root 是整棵 Trie 的根节点。

它本身不存任何字符，只是所有字符串的起点。

所有插入、查找操作，都是从 root 开始，一层一层往下走。

一、insert 操作

代码

public void insert(String word) {
    Node cur = root;
    for (char c : word.toCharArray()) {
        c -= 'a';
        if (cur.son[c] == null) {
            cur.son[c] = new Node(); 
        }
        cur = cur.son[c];
    }
    cur.end = true;
}

思路解释

插入一个单词时，我们从根节点出发，按字符一个一个往下走。

对于当前字符：

如果对应的子节点不存在，就创建新节点
如果已经存在，就直接复用

最后走完整个单词之后，把当前节点标记为单词结尾。

逐步理解

比如插入 apple：

第一步：处理 `'a'`

从 root 出发，看 root.son['a' - 'a'] 是否存在。

如果不存在，就创建一个表示 'a' 的节点。

第二步：处理第一个 `'p'`

从 'a' 节点继续往下，看它的 'p' 分支是否存在。

不存在就创建。

第三步：继续处理后面的字符

按照同样的方式，把整条路径建出来。

第四步：标记结尾

当所有字符都处理完后：

cur.end = true;

表示这个节点对应一个完整单词。

为什么不能只靠路径判断完整单词

比如我们插入了 apple，那么 Trie 中肯定存在路径：

a -> p -> p

但这并不代表 app 一定存在。

所以当我们要查找 app 是否是一个完整单词时，不能只看路径是否存在，还要看最后那个节点的 end 是否为 true。

这也是为什么 end 标记必不可少。

二、search 操作

代码

public boolean search(String word) {
    return find(word) == 2;
}

search 用来判断：

某个字符串是否作为完整单词存在于 Trie 中。

它本身没有重复写逻辑，而是直接调用了 find(word)。

如果 find(word) 返回 2，说明：

路径存在
并且最后节点是单词结尾

那么 search 返回 true。

三、startsWith 操作

代码

public boolean startsWith(String prefix) {
    return find(prefix) != 0;
}

startsWith 用来判断：

是否存在某个已经插入的单词，前缀是 prefix。

这里只要这条路径存在就可以了，不要求它一定是完整单词。

所以：

返回 1 说明只是前缀存在
返回 2 说明前缀存在，而且本身还是完整单词

这两种情况都应该返回 true。

四、find 方法是整份代码的核心

代码

private int find(String word) {
    Node cur = root;
    for (char c : word.toCharArray()) {
        c -= 'a';
        if (cur.son[c] == null) {
            return 0;
        }
        cur = cur.son[c];
    }
    return cur.end ? 2 : 1;
}

`find` 返回值分别表示什么

这份代码设计得很巧妙，用一个 find 方法统一处理两种查询。

返回值有三种：

0：路径不存在
1：路径存在，但不是完整单词结尾，只是前缀
2：路径存在，并且是完整单词结尾

这样：

search(word) 只需要判断是否等于 2
startsWith(prefix) 只需要判断是否不等于 0

代码逻辑

1. 从根节点开始

Node cur = root;

2. 逐字符往下找

for (char c : word.toCharArray()) {
    c -= 'a';
    if (cur.son[c] == null) {
        return 0;
    }
    cur = cur.son[c];
}

如果中途某个字符对应的子节点不存在，说明这条路径根本不存在，直接返回 0。

3. 判断最后节点是不是单词结尾

return cur.end ? 2 : 1;

如果路径能走完：

cur.end == true，说明这个字符串是完整单词，返回 2
否则说明它只是某个单词的前缀，返回 1

示例推演

假设依次插入：

apple
app

查询 `search("apple")`

路径存在，并且最后 e 节点的 end = true，所以返回 true。

查询 `search("app")`

路径存在，并且第二个 p 节点的 end = true，所以返回 true。

查询 `search("ap")`

路径存在，但 p 节点不是完整单词结尾，所以 find("ap") 返回 1，最终 search("ap") 返回 false。

查询 `startsWith("ap")`

虽然 ap 不是完整单词，但这条前缀路径存在，所以返回 true。

查询 `startsWith("abc")`

路径中断，返回 false。

这道题为什么适合用 Trie

如果用 HashSet<String>：

search(word) 很好做
但 startsWith(prefix) 就不方便

因为你需要枚举所有单词，看有没有哪个单词以前缀开头。

而 Trie 的结构天然就是按前缀组织的，所以：

查某个单词是否存在：走一遍路径
查某个前缀是否存在：也走一遍路径

都非常自然。

复杂度分析

假设单词长度为 L。

insert

时间复杂度：O(L) 空间复杂度：最坏情况下为 O(L)（当路径都需要新建节点时）

search

时间复杂度：O(L) 空间复杂度：O(1)（不算 Trie 本身占用的空间）

startsWith

时间复杂度：O(L) 空间复杂度：O(1)

这份写法的优点

你这份代码有两个很好的点。

1. 结构清晰

insert 负责插入
search 负责完整单词查询
startsWith 负责前缀查询
find 把公共逻辑抽出来复用

这样代码不会重复，逻辑也很统一。

2. `find` 的返回值设计很巧妙

很多写法会分别写两个查找函数：

一个给 search
一个给 startsWith

但你这里用 0 / 1 / 2 三种状态统一表达：

不存在
是前缀
是完整单词

这让整体实现更加简洁。

总结

这道题的核心就是理解 Trie 的节点设计和路径含义：

每个节点有 26 个分支，对应 26 个小写字母
每个单词从根节点开始，一层一层往下走
插入时，不存在的节点就创建
查找时，如果路径中断就说明不存在
end 用来区分“只是前缀”还是“完整单词”

你可以把这道题总结成一句话：

Trie 就是一棵按字符逐层存储字符串的树，用来高效处理单词查询和前缀查询。

这是一道非常经典的数据结构设计题，后面很多字符串题，比如：

单词搜索
替换单词
单词字典
最长公共前缀类问题

都会和 Trie 有关系，所以这一题非常值得彻底吃透。