小秋今天去面试了,面试官问了一个与敏感词过滤演算法相关的问题,然而小秋对敏感词过滤演算法一点也没听说过。于是,有了以下事情的发生…..
面试官开怼
面试官:玩过王者荣耀吧?了解过敏感词过滤吗?,例如在游戏里,如果我们发送「你在干嘛?麻痹演员啊你?」,由于「麻痹」是一个敏感词,所以当你把聊天发出来之后,我们会用「」来代表「麻痹」这次词,所以发送出来的聊天会变成这样:「你在干嘛?演员啊你?」。
小秋:听说过啊,在各大社区也经常看到,例如评论一个问题等,一些粗话经常被过滤掉了。
面试官:嗯,如果我给你一段文字,以及给你一些需要过滤的敏感词,你会怎么来实现这个敏感词过滤的演算法呢?例如我给你一段字元串「abcdefghi",以及三个敏感词"de", "bca", "bcf"。
小秋:(敏感词过来演算法??不就是字元串匹配吗?)我可以通过字元串匹配演算法,例如在字元串」abcdefghi"在查找是否存在字串「de",如果找到了就把」de「用""代替。通过三次匹配之后,接变成这样了:「abcfghi"。
面试官:可以说说你采用哪种字元串匹配演算法吗?
小秋:最简单的方法就是采用两个for循环保留求解了,不过每次匹配的都时间复杂度为O(n*m),我可以采用 KMP 字元串匹配演算法,这样时间复杂度是 O(m+n)。
n 表示字元串的长度,m 表示每个敏感词的长度。
面试官:这是一个方法,对于敏感词过滤,你还有其他方法吗?
小秋:(其他方法?说实话,我也觉得不是采用这种 KMP 演算法来匹配的了,可是,之前也没去了解过敏感词,这下要凉)对敏感词过来之前也没了解过,暂时没想到其他方法。
trie 树
面试官:了解过 trie 树吗?
小秋:(嘿嘿,数据结构这方法,我得争气点)了解过,我还用代码实现过。
面试官:可以说说它的特点吗?
小秋:trie 树也称为字典树、单词查找树,最大的特点就是共享字元串的公共前缀来达到节省空间的目的了。例如,字元串 "abc"和"abd"构成的 trie 树如下: