[TOC]
前缀树
trie 树也称为字典树、单词查找树，最大的特点就是共享字符串的公共前缀来达到节省空间的目的了。例如，字符串 “abc”和”abd”构成的 trie 树如下：
trie 树来实现敏感词过滤
三个敏感词：”de”, “bca”, “bcf” 建立一颗 trie 树
接着我们可以采用三个指针来遍历
1、首先指针 p1 指向 root，指针 p2 和 p3 指向字符串第一个字符
2、然后从字符串的 a 开始，检测有没有以 a 作为前缀的敏感词，直接判断 p1 的孩子节点中是否有 a 这个节点就可以了，显然这里没有。接着把指针 p2 和 p3 向右移动一格。
3、然后从字符串 b 开始查找，看看是否有以 b 作为前缀的字符串，p1 的孩子节点中有 b，这时，我们把 p1 指向节点 b，p2 向右移动一格，不过，p3不动。
4、判断 p1 的孩子节点中是否存在 p2 指向的字符c，显然有。我们把 p1 指向节点 c，p2 向右移动一格，p3不动。
5、判断 p1 的孩子节点中是否存在 p2 指向的字符d，这里没有。这意味着，不存在以字符b作为前缀的敏感词。这时我们把p2和p3都移向字符c，p1 还是还原到最开始指向 root。
6、和前面的步骤一样，判断有没以 c 作为前缀的字符串，显然这里没有，所以把 p2 和 p3 移到字符 d。
7、然后从字符串 d 开始查找，看看是否有以 d 作为前缀的字符串，p1 的孩子节点中有 d，这时，我们把 p1 指向节点 b，p2 向右移动一格，不过，p3和刚才一样不动。（看到这里，我猜你已经懂了）
8、判断 p1 的孩子节点中是否存在 p2 指向的字符e，显然有。我们把 p1 指向节点 e，并且，这里e是最后一个节点了，查找结束，所以存在敏感词de，即 p3 和 p2 这个区间指向的就是敏感词了，把 p2 和 p3 指向的区间那些字符替换成 *。并且把 p2 和 p3 移向字符 f。如下：
9、接着还是重复同样的步骤，知道 p3 指向最后一个字符。
复杂度分析
面试官：可以说说时间复杂度吗？
小秋：如果敏感词的长度为 m，则每个敏感词的查找时间复杂度是 O(m)，字符串的长度为 n，我们需要遍历 n 遍，所以敏感词查找这个过程的时间复杂度是 O(n * m)。如果有 t 个敏感词的话，构建 trie 树的时间复杂度是 O(t * m)。
如果让你来 构建 trie 树，你会用什么数据结构来实现？
小秋：我一般使用 Java，我会采用 HashMap 来实现，因为一个节点的字节点个数未知，采用 HashMap 可以动态拓展，而且可以在 O(1) 复杂度内判断某个子节点是否存在。