字节二面：什么是trie树及其应用本文转载请联系帅迪万编程公众号。你只需要了解Trie树的原理和应用即可。有时你会在面试中被问到。接下来我就用面试的情况给大家讲解一下trie树。采访者：你玩过王者荣耀吗？你了解过敏感词过滤吗？比如在游戏中，如果我们发送“你在做什么？麻痹演员，你？”，由于“麻痹”是一个敏感词，所以当你发出聊天后，我们会用“**”来代表“瘫痪”一词，所以发送的聊天将变成这样：“你在做什么？**演员，你？”。小秋：听说过，在各个社区也经常看到，比如评论一个问题等等，经常会过滤掉一些粗话。面试官：好吧，如果我给你一段文字和一些需要过滤的敏感词，你会如何实现这个敏感词过滤算法？比如我给你一个字符串“abcdefghi”，以及三个敏感词“de”、“bca”、“bcf”。小秋：（敏感词来算法？不就是字符串匹配吗？）我可以用字符串匹配算法，比如，查找字符串“abcdefghi”中是否存在字符串“de”，如果找到，就把“de””用...代替。匹配3次后变成这样：“abc**fghi”。面试官：你用的是哪种字符串匹配算法？小秋：最简单的方法是用2次代替循环保持解决方案，但是每次匹配的时间复杂度是O(n*m)，我可以使用KMP字符串匹配算法，所以时间复杂度是O(m+n)。n代表字符串的长度，并且m代表每个敏感词的长度面试官：这是一种方法，你们有没有其他过滤敏感词的方法？,不过没试过敏感词都学过，这次就爽了）来之前从来没听懂过敏感词here，暂时还没有想到其他的方法。Trie树面试官：你听说过Trie树吗？小秋：（哎，我得对数据结构的方法更有信心了）我知道，而且我已经用代码实现了。采访者：能谈谈它的特点吗？小秋：Trie树也叫词典树、查词树。最大的特点是它们共享字符串的公共前缀以节省空间。例如，由字符串“abc”和“abd”组成的trie树如下：trie树的根节点不存储任何数据，每个分支代表一个完整的字符串。就像abc和abd有共同的前缀ab，所以我们可以共享节点ab。如果我再插入abf，它就变成这样：如果我再插入bc，它就变成这样（bc和其他三个字符串没有共同的前缀）。面试官：那如果我们再插入字符串“ab”呢？小秋：我差点说每一个分支里面也可能包含一个完整的字符串，所以我们可以把那些是某个字符串结尾的节点做一个节点Tags，比如abc,abd,abf都包含字符串ab，所以我们可以在节点b这里做一个标签。如下（我用红色作为标记）：面试官：你能告诉我trie树的应用有哪些？小秋：trie最大的特点就是使用了字符串的公共前缀，就像我们有时候在百度、谷歌输入某个key写词的时候，它会帮我们列出很多相关的信息，这是通过特里树。小秋：（咦？Trie又叫查词树，刚才好像可以用trie来实现敏感词匹配？面试官是不是无缘无故提到了trie树？）面试官：刚才的敏感词过滤现在其实是可以用一个trie来实现的，你知道怎么实现吗？一棵trie树用来过滤敏感词想一想……我知道，我可以这样实现：首先，用你给我的三个敏感词：“de”、“bca”、“bcf”构建一个trie树，如下：那我们就可以用三指针来遍历了，我直接用你上面给你的例子来演示。1.首先指针p1指向根，指针p2和p3指向字符串的第一个字符2.然后，从字符串中的a开始，检测是否有以a为前缀的敏感词，直接判断p1的子节点中有没有a这个节点就好了，显然这里没有。然后将指针p2和p3向右移动一个空格。3、然后从字符串b开始查找，看是否有以b为前缀的字符串。p1的子节点中有b。这时，我们将p1指向节点b，将p2向右移动。但是，p3不要动。4.判断p2指向的字符c是否存在于p1的子节点中，显然有。我们将p1指向节点c，p2向右移动一格，p3不移动。5、判断p2指向的字符d是否存在于p1的子节点中，而这里不存在。这意味着没有以字符b为前缀的敏感词。这时候我们把p2和p3都移动到字符c，p1还是恢复到一开始指向root。6、和上一步一样，判断是否有以c为前缀的字符串，显然这里没有，所以将p2和p3移到字符d处。7、然后从字符串d开始查找，看是否有以d为前缀的字符串。p1的子节点中有d。此时我们将p1指向节点d，将p2向右移动。不过，p3还是和以前一样。（看到这里，估计你已经明白了）8、判断p2指向的字符e是否存在于p1的子节点中，显然是有的。我们把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树的时间复杂度可以忽略不计，因为我们可以一开始就构建一个trie树，以后可以重复使用无数次。刚才的kmp算法的时间复杂度是t*(m+n)，但是kmp需要维护下一个数组，比较占空间，而且在实际情况下，敏感词t的个数比较多，而n是比较小。10.如果让你构建一个trie树，你会用什么数据结构来实现它？小秋：我一般用Java，我会用HashMap来实现，因为一个节点的字节数是未知的，而HashMap可以用来动态扩容，可以在O(1)内判断某个子节点是否存在复杂。面试官：嗯，回去等通知吧。综上所述，今天主要介绍trie树和trie树的一些应用，以及如何通过trie树过滤敏感词。至于代码的实现，这里就不给出了。在实现的时候，为了防止这种“麻痹”或者“瘫痪”等，我们还需要过滤特殊字符等等，有兴趣的可以实现一波。
