Trie 树也称为字典树、单词查找树，最大的特点就是共享字符串的公共前缀，这样可以达到节省空间的目的。像我们在使用搜索引擎输入某些关键字的时候，搜索引擎会自动弹出一些相关的信息，这些都是通过 Trie 树实现的。
image
Trie 树的数据结构
Trie 树的根节点不存任何数据，每个分支都代表一个完整的字符串。来看看 Trie 树的结构：
image
从上图可以归纳出Trie树的基本性质：
- 根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
- 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
- 每个节点的所有子节点包含的字符互不相同。
- 从第一字符开始有连续重复的字符只占用一个节点，比如上面的 to 和 ten，中重复的单词 t 只占用了一个节点。
从这几条基本性质我们可以抽象出节点的 class 属性：
- 是否为叶子节点的标志位 isWord。
- 既能存储当前节点的值也能存储其所有的子节点的数据结构HashMap。
先从稍微简单的实现开始
在 Java 中，Trie 树可以使用 HashMap 实现，因为一个节点的子节点个数未知，而 HashMap 可以动态扩展，而且可以在 O(1) 的时间复杂度内判断某个子节点是否存在。以 LeetCode 208 为例，来看看这种实现方式。
image
首先定义 Trie 树的节点，节点的结构为 HashMap，key 为字符串中的字符，value 为这个节点的子节点。
class TrieNode {
// 子节点(key是下级字符，value是下级节点)
private Map<Character, TrieNode> subNodes = new HashMap<>();
// 添加子节点
public void addSubNode(Character c, TrieNode subNode) {
subNodes.put(c, subNode);
}
// 获取子节点
public TrieNode getSubNode(Character c) {
return subNodes.get(c);
}
}
再来看看 Trie 树的主函数，在初始化树时，使用构造函数构造一个不存数据的根节点。在插入字符串时，从根节点开始判断树中是否已经包含了这个字符串的当前字符，如果不存在这个字符则新建节点保存当前字符，插入结束的时候设置结束标识，这里简单的用'#'来标记。
search() 和 startsWith() 函数也是类似，从根节点开始查找 HashMap 中是否存在对应的子节点。这两个函数的唯一区别是在字符串遍历完成的时候，search() 需要判断当前字符是否已经走到了 Trie 树的叶子节点，而 startsWith() 函数不需要。
class Trie {
TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode curNode = this.root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
TrieNode subNode = curNode.getSubNode(c);
// 如果没有这个节点则新建
if (subNode == null) {
subNode = new TrieNode();
curNode.addSubNode(c, subNode);
}
// 指向子节点，进入下一循环
curNode = subNode;
}
// 设置结束标识
curNode.addSubNode('#', new TrieNode());
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode curNode = this.root;
for (int i = 0; i < word.length(); i++) {
curNode = curNode.getSubNode(word.charAt(i));
if (curNode == null) return false;
}
return curNode.getSubNode('#') != null;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode curNode = this.root;
for (int i = 0; i < prefix.length(); i++) {
curNode = curNode.getSubNode(prefix.charAt(i));
if (curNode == null) return false;
}
return true;
}
}
进一步实现敏感词过滤
在实现敏感词过滤前，首先需要初始化 Trie 树，将所有敏感词作为字符串全部插入到 Trie 树中。
其实原理还是和之前一样的，只不过相对于上面的代码来说，我们需要多增加一个指针。因为敏感词在字符串的位置我们是不知道的嘛，所以我们只能增加一个指针，对整个字符串进行遍历，寻找敏感词开始的位置，剩下的逻辑就和上面的代码相似了，如下图所示。这里假设在 Trie 树中已经初始化好了 bca、bcf、de 这几个敏感词。
image
首先 p1 指针指向 root，指针 p2 和 p3 指向字符串中的第一个字符。算法从字符 a 开始，检测有没有以 a 作为前缀的敏感词，在这里就直接判断 root 中有没有 a 这个子节点即可。没有的话将 p2 和 p3 同时右移，而如果存在以 a 作为前缀的敏感词，那么就只右移 p3 继续判断 p2 和 p3 之间的这个字符串是否是敏感词。如果在字符串中找到敏感词，那么可以用其他字符串如 *** 代替。接下来不断循环直到整个字符串遍历完成就可以了。
这样的算法时间复杂度是多少呢？构建敏感词的时间复杂度是可以忽略不计的，因为构建完成后我们是可以无数次使用的。所以我们来看看查找敏感词的时间复杂度。如果字符串的长度为 n，而每个敏感词查找的时间复杂度是 O(m)，我们需要对字符串遍历 n 遍，所以查找敏感词的这个过程的时间复杂度为 O(m * n)。
网友评论