Info

数据结构精品课 和 递归算法专题课 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》 出版，签名版限时半价！

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
1804. Implement Trie II (Prefix Tree)🔒	1804. 实现 Trie （前缀树） II🔒	🟠
208. Implement Trie (Prefix Tree)	208. 实现 Trie (前缀树)	🟠
211. Design Add and Search Words Data Structure	211. 添加与搜索单词 - 数据结构设计	🟠
648. Replace Words	648. 单词替换	🟠
677. Map Sum Pairs	677. 键值映射	🟠
-	剑指 Offer II 062. 实现前缀树	🟠
-	剑指 Offer II 063. 替换单词	🟠
-	剑指 Offer II 066. 单词之和	🟠

Tip

本文有视频版：动手实现字典树。

Trie 树又叫字典树、前缀树、单词查找树，是一种二叉树衍生出来的高级数据结构，主要应用场景是处理字符串前缀相关的操作。

我是在《算法 4》第一次学到这种数据结构，不过书中的讲解不是特别通俗易懂，所以本文按照我的逻辑帮大家重新梳理一遍 Trie 树的原理，并基于《算法 4》的代码实现一套更通用易懂的代码模板，用于处理力扣上一系列字符串前缀问题。

阅读本文之前希望你读过我旧文讲过的 回溯算法代码模板 和 手把手刷二叉树（总结篇）。

本文主要分三部分：

1、讲解 Trie 树的工作原理。

2、给出一套 TrieMap 和 TrieSet 的代码模板，实现几个常用 API。

3、实践环节，直接套代码模板秒杀 5 道算法题。本来可以秒杀七八道题，篇幅考虑，剩下的我集成到 刷题插件 中。

关于 Map 和 Set，是两个抽象数据结构（接口），Map 存储一个键值对集合，其中键不重复，Set 存储一个不重复的元素集合。

常见的 Map 和 Set 的底层实现原理有哈希表和二叉搜索树两种，比如 Java 的 HashMap/HashSet 和 C++ 的 unorderd_map/unordered_set 底层就是用哈希表实现，而 Java 的 TreeMap/TreeSet 和 C++ 的 map/set 底层使用红黑树这种自平衡 BST 实现的。

而本文实现的 TrieSet/TrieMap 底层则用 Trie 树这种结构来实现。

了解数据结构的读者应该知道，本质上 Set 可以视为一种特殊的 Map，Set 其实就是 Map 中的键。

所以本文先实现 TrieMap，然后在 TrieMap 的基础上封装出 TrieSet。

Note

为了模板通用性的考虑，后文会用到 Java 的泛型，也就是用尖括号 <> 指定的类型变量。这些类型变量的作用是指定我们实现的容器中存储的数据类型，类比 Java 标准库的那些容器的用法应该不难理解。

前文 学习数据结构的框架思维 说过，各种乱七八糟的结构都是为了在「特定场景」下尽可能高效地进行增删查改。

你比如 HashMap<K, V> 的优势是能够在 O(1) 时间通过键查找对应的值，但要求键的类型 K 必须是「可哈希」的；而 TreeMap<K, V> 的特点是方便根据键的大小进行操作，但要求键的类型 K 必须是「可比较」的。

本文要实现的 TrieMap 也是类似的，由于 Trie 树原理，我们要求 TrieMap<V> 的键必须是字符串类型，值的类型 V 可以随意。

接下来我们了解一下 Trie 树的原理，看看为什么这种数据结构能够高效操作字符串。

本文剩余内容为会员内容，请先购买 网站会员 ，然后 借助 Chrome 插件解锁网页 或者 点这里 跳转小鹅通查看。