字典树概念与题型解析
来源 | 五分钟学算法
这次讲一个不经常被人提起的数据结构 - 字典树，虽说知名度不高，但是这个数据结构可以解决其他数据结构所不能解决，或者是比较难解决的问题，而且性能方面，相对于其他的功能类似的数据结构会更优，文章会从概念与基本实现，性能分析，题型解析三大方向来介绍字典树。
概念
在讲什么是字典树之前，请你回忆下，你曾今是否翻阅过纸质版的英文字典？你是如何在字典中定位一个单词呢？这么说可能不太直观，我举个例子好了，比如要在字典中寻找 hello 这个单词，我可能会先找到 h 开头的单词出现的大致范围，然后我会把我的注意力从 h 上转到 e，也就是在所有开头是 h 的单词中寻找第二个字母是 e 的单词，也就是找 he 开头的单词出现的范围，这个范围会比之前 h 开头的单词的范围更小，找到了 he 的范围，我们又会去寻找 l，以此类推，由此可以总结出我们的寻找路线如下：
h -> he -> hel -> hell -> hello
到这里，不知道你有没有发现一点，我们在字典中寻找一个单词的过程，其实就是一个不断寻找这个单词前缀的过程。其实字典树干的就是这个事情，不断寻找前缀，直到找到需要找的单词，因此 字典树又称前缀树（prefix tree）。
相信通过上面的描述，你应该对字典树有了一个初步的认识。
那么现在的问题是，我们该如何将这个寻找前缀的过程放到树上进行呢？
树有两个东西，一个是节点，另外一个是边，节点之间通过边进行连接。通过之前的描述，你可以看到，其实我们每次在寻找的是一个个字符，将这个字符和之前找到过的所有字符拼接在一起就成了下一个前缀，每个字典树节点里面其实可以存放字符，然后一条由根节点往下的路径把路径上所有的节点串起来，在树中，边其实是有方向性的，就是 parent -> child，因为除根节点外，每个节点只会有一个 parent 节点，那么就是说从根节点到树上的任意节点，只可能存在唯一的一条路径。
这条路径可以唯一地代表一个单词。
你可以看到，根节点是我们的起始点，终点可能是树中的任意节点，那么问题来了，刚刚的例子中，hel 也是一个从根节点到树中某节点的路径，但是 hel 不是单词啊。这个好解决，我们可以在节点中用一个 boolean 变量来表示以该节点结尾的这条路径是不是一个单词。
通过上面的分析，我们可以把基本的字典树节点代码写出来：
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isWordOrNot = false;
}
你可以看到，字典树其实是一个多叉树，因为英文中，如果不区分大小写的话，只有 26 个字母，因此每个节点最多也只有 26 个子节点，当然，这里你也可以使用哈希表来代替数组，children 中只保存存在的情况，会有空间上面的优势：
class TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
boolean isWordOrNot = false;
}
另外就是之前提到的一个变量，isWordOrNot，用来确定从根节点到当前节点的这条路径能不能代表一个单词。
这里你可能会问，我们需不需要把当前节点代表的字符也给存在节点中，答案是不需要。
理由也很简单，我们并不是孤立地去看待每个节点，不管是寻找单词，还是寻找前缀，我们都是从上往下去找的，children 数组的下标就已经表示下一层节点的字符了，比如我们从根节点去找 hello 的第一个字符，也就是 h，我们会直接访问 root.children['h' - 'a'] 所代表的节点。
因为是从上到下的关系，下一层的信息依赖于上一层的 children 数组，根节点并没有上一层，因此字典树的根节点并不代表任何字符，你可以把其仅仅当作是一个入口。
有了树节点，那么我们就可以通过输入的单词去构建树了，你也可以把它理解为在树上构建路径，代码如下：
private TrieNode root = new TrieNode();
public void addWord(String word) {
TrieNode pointer = root;
for (char c : word.toCharArray()) {
if (pointer.children[c - 'a'] == null) {
pointer.children[c - 'a'] = new TrieNode();
}
pointer = pointer.children[c - 'a'];
}
pointer.isWordOrNot = true;
}
构建的时间复杂度其实是依赖于字符串的长度，也就是 O(L)，这里的 L 表示的是字符串的长度。
另外查找一个单词其实和插入一个单词类似，就是确认一条路径是否存在的过程，这部分的代码我会在后面的题型解析部分展示。通过上面的分析，我们可以总结出字典树的两大基本用法：
- 确认一个单词是否在字典中存在
- 确认字典中是否含有某前缀的单词
关于第二点可以扩展一下：
- 求得字典中含有某前缀的所有单词
- 计算字典中含有某前缀的单词的个数
- 计算字典中含有某前缀的单词的出现频率
字典树性能分析
通过前面的介绍，你不难发现，字典树的查找和插入单词的时间复杂度都是 O(L)，这个 L 是单词的长度。但是光看这个时间复杂度并不能完全反映出字典树的性能，俗话说没有对比就没有伤害，我们就对比一下具有相同或者相似功能的其他数据结构是什么一个情况。对于 “确认一个字符串是否存在” 这个功能，我想你肯定会想到哈希表这个数据结构，那你可以思考下哈希表干这个事情的时间复杂度是多少呢？O(1)？如果你对哈希表的设计有一点了解的话，你大概率上不会给出这么一个答案，当你在哈希表里面寻找一个元素，哈希表其实做了两件事情：
- 计算元素的哈希值
- 查找并确认元素是否存在
对于一个长度为 L 的字符，上面这两个操作的时间复杂度均不是 O(1) 的，首先来看计算元素的哈希值，不管你使用什么样的哈希函数，计算哈希值这个过程都是要基于元素本身的，因为对于相同的元素，哈希值肯定相同。因此对于一个输入字符串，如果需要减少哈希冲突，哈希函数最起码都会将整个字符串给扫一遍，那这里的时间复杂度就是 O(L)。第二个操作，寻找并确认元素，我们根据哈希值找到对应的位置，但是由于哈希冲突一直存在，我们这个时候必须去比较判断当前位置的字符串是不是我们要找的，两个字符串的比较只能是字符挨个比较，时间复杂度还是 O(L)。当然我说的这些还是最理想的情况，如果有冲突，那么这个时间复杂度还会更高。因此，从时间上面看，哈希表并不会比字典树更优。
说完了时间，那么空间呢？请看下面的一个单词列表：
[aaaaaaaab,aaaaa,aaaaaaa,aaaa]
当然我这里为了方便你理解，例子举的极端了些，如果这些字符串存在哈希表中，那么实际存储的内容将会是：
aaaaaaaab,aaaaa,aaaaaaa,aaaa
如果存在字典树中呢？
aaaaaaaab
由于字典树具有字符串前缀的相关功能，所有单词的字符并不会全都存储，具有相同前缀的单词的存储其实是会被压缩的，当然这只是形象上讨论空间，由于每个 TrieNode 还有 children，无法精确对比，但是在字符种类有限的情况下字典树的优势更明显。
因此，你可以看到，空间上面，相比于哈希表，字典树其实是更优的。而且，除了判断一个字符串是否存在，字典树比哈希表还多具备了一个前缀查找的功能。通过这么一分析，其实字典树的性能比我们熟知的哈希表是要更优的，至少是在字符串查找这个问题上。
例题解析
LeetCode 第 208 号问题：实现 Trie (前缀树)。
题目描述
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
题目分析
实现一个字典树，这个字典树具备添加，查找，以及查找前缀这几个功能。查找和查找前缀的区别是，查找必须保证找到的节点必须能代表单词，查找前缀的要求会宽松些，只需要确定节点存在即可。
参考代码
class Trie {
/** Initialize your data structure here. */
private final int ALPHABET_SIZE = 26;
private class TrieNode {
private TrieNode[] children = new TrieNode[ALPHABET_SIZE];
private boolean isWordOrNot = false;
}
private TrieNode root;
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode pointer = root;
for (char c : word.toCharArray()) {
if (pointer.children[c - 'a'] == null) {
pointer.children[c - 'a'] = new TrieNode();
}
pointer = pointer.children[c - 'a'];
}
pointer.isWordOrNot = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode pointer = this.root;
for (char c : word.toCharArray()) {
if (pointer.children[c - 'a'] == null) {
return false;
}
pointer = pointer.children[c - 'a'];
}
return pointer.isWordOrNot;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode pointer = root;
for (char c : prefix.toCharArray()) {
if (pointer.children[c - 'a'] == null) {
return false;
}
pointer = pointer.children[c - 'a'];
}
return true;
}
}
LeetCode 第 211 号问题：添加与搜索单词 - 数据结构设计。
题目描述
设计一个支持以下两种操作的数据结构：
void addWord(word)
bool search(word)
search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。. 可以表示任何一个字母。
示例:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
题目分析
设计一个数据结构，这个数据可以添加单词，还有可以查找输入单词是否存在，但是这里查找的输入单词中可以含有特殊字符 '.'，'.' 可以表示任意字符。字典树其余部分还是不变，主要是查找部分需要做些调整，这里写了一个递归深度优先搜索的方式去查找，和二叉树遍历的方式类似，只不过这里变成了多叉树。另外就是遇到当前字符是 '.' 时，需要把当前节点的所有存在的子节点都考虑一遍。
参考代码
class WordDictionary {
private class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isWord = false;
char c;
TrieNode() {}
TrieNode(char c) {
this.c = c;
}
}
private TrieNode root;
/** Initialize your data structure here. */
public WordDictionary() {
root = new TrieNode();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
if (word == null || word.length() == 0) {
return;
}
char[] wordArr = word.toCharArray();
TrieNode pointer = root;
for (int i = 0; i < wordArr.length; ++i) {
if (pointer.children[wordArr[i] - 'a'] == null) {
pointer.children[wordArr[i] - 'a'] = new TrieNode(wordArr[i]);
}
pointer = pointer.children[wordArr[i] - 'a'];
}
pointer.isWord = true;
}
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
public boolean search(String word) {
return helper(0, word.toCharArray(), root);
}
private boolean helper(int index, char[] word, TrieNode root) {
if (index == word.length) {
return root.isWord;
}
char curC = word[index];
if (curC != '.') {
if (root.children[curC - 'a'] != null) {
return helper(index + 1, word, root.children[curC - 'a']);
} else {
return false;
}
}
if (curC == '.') {
for (int i = 0; i < root.children.length; ++i) {
if (root.children[i] != null && helper(index + 1, word, root.children[i])) {
return true;
}
}
}
return false;
}
}
总结
字典树在实际当中也会被用到，比如 auto complete，也就是 搜索引擎的自动补全功能，如果你了解了字典树，相信你应该不难理解这个应用是如何做到的。如果一个问题当中有涉及到字符串前缀等相关的信息，那么你就需要想到字典树，多说无用，动手去实现一下，你会有更深的理解。
腾讯云开发者
