Trie树
Trie树
完成leetcode里面trie树的题目后，再了解下trie树的日常应用。
https://leetcode-cn.com/problems/implement-trie-prefix-tree/
手写出trie树的感觉不错，以前都是看介绍，没机会手写来证明自己已经掌握了，总归并不踏实。
没想到搜索引擎的自动补全，9宫格打字法预测，竟然都是用Trie树实现的。
不过现在对KMP和AC自动机还不够了解，得看看有没有机会在leetcode里找到题目做，不然纯看课本真是很难掌握。
trie树的一般应用
使用trie树构建敏感词过滤
- 游戏中的敏感词过滤是如何实现的？
(https://cloud.tencent.com/developer/article/1427110)
原来用来构建trie树的是敏感词集合
- Serverless 实战：3 分钟实现文本敏感词过滤
https://www.infoq.cn/article/d0JZjH0lpTTJqhj32VG1
使用Trie树构建的敏感词列表，在替换的时候是O(N * L)的复杂度，L为敏感词中最长的元素。并没有用复杂的KMP自动机，而是用双指针迭代，每个起始位置都进行判断，如果不存在，则跳到下一个位置。
也有使用AC自动机的，不过这个就没时间去看清楚了，毕竟我对KMP算法还不能手写，不够熟悉实现的具体。