type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
Trie 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。
这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
实现 Trie 类：
Trie()初始化前缀树对象。
void insert(String word)向前缀树中插入字符串word。
boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。
boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false。
示例：
提示：
1 <= word.length, prefix.length <= 2000
word和prefix仅由小写英文字母组成
insert、search和startsWith调用次数 总计 不超过3 * $10^4$次
解法一：定长数组
可以把整个 Trie 想象成一个 “多叉树”，每个节点对应 26 个可能的分支（小写英文字母 a-z）。
插入一个单词的过程，其实就是沿着路径不断往下, 没有对应字母就建新节点，直到单词末尾，并把最后一个节点标记成
isEnd = True。这样再去查询时，只要走相同路径并且找到
isEnd = True，就能判断单词存在。查找前缀的逻辑一模一样，只不过不要求结尾节点是单词的末尾，只要前缀路径能走到就算存在。
优点是查找快，缺点是空指针多，较费内存（特别是分支稀疏时）。
复杂度
- 单次
insert/search/startsWith：O(L)（L 为字符串长度）
- 空间：最坏 O(T)（T 为全部插入字符数）
解法二：哈希字典 （推荐）
很多分支其实很稀疏，解法一用数组会浪费大量空位。
按需生成子节点，只在有字符时才建对应分支，更灵活省空间。
节点不再是一个固定大小的数组，而是个字典
{字符: 子节点}。每次插入字符时，用
children[char] 来表示分支；单词结束也是通过一个特殊标记（如
'#' 或 isword=True）来标记。和解法一一样，插入/查询都还是按字符一层一层走，只是每步多一次哈希查找。
复杂度
- 单次操作：O(L)
- 空间：最坏O(T)
工程级扩展
1. 压缩路径（Radix Tree / Patricia Trie）
现实里的字符串往往共享很长的公共前缀。把这些“一路单链”的节点一个个开出来太浪费了。
合并只有单个子节点的连续链，减少节点数量。例如从
a→p→p 压成一条边 "app"。节点存储整个字符串片段而不是单个字符。
插入查询依然 O(L)，但常数项比原始 Trie 小很多，极大节省空间。
2. 双数组 Trie
用两个数组
base[] 和 check[] 表示树结构。高度压缩、省内存、适合纯读取型应用。
查询仍然 O(L)，但插入复杂，适合离线构建。
3. FST (Finite State Transducer)
- 把 Trie 压缩成最小有向无环图 (DAWG/FST)。
- Lucene、搜索引擎常用，只读场景性能极好。
- 空间可到每字符 1~2 字节量级。
4. 大规模数据的 LSM 层式方案
- 内存中维护可变小 Trie；
- 满了就 flush 到磁盘形成只读段，用 Bloom Filter 做快速过滤。
- 平衡了“读多写多且放不下内存”的场景。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-208-实现-trie
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 206] 反转链表
下一篇
[Leetcode 236] 二叉树的最近公共祖先