大家好，又见面了，我是你们的朋友全栈君。
【字典树】(Trie Tree) 是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串）。 它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。 ——百度 · 百科
还好，它还有其他的名字，更能表述出它的实质：
接下来将对经典的字典树进行代码实现；接着做几个变体题目深入理解字典树的强大；最后回到日常生活，瞧瞧字典树怎样融入到了我们的生活之中 >_<
首先，数据结构嘛，肯定是要先构建节点（Node）;
弄清了节点的结构和含义，一棵树（Tree）的构建就会水到渠成
这里有两个关键点：
构建好了节点，下面开始构建树，并写出树的一些方法 ↓
变式1：利用字典树的构造过程——忽略后缀单词
【Leetcode_820】单词的压缩 给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。 例如，如果这个列表是 [“time”, “me”, “bell”]，我们就可以将其表示为 S = “time#bell#” 和 indexes = [0, 2, 5]。# 表示一个结束位置 那么成功对给定单词列表进行编码的最小字符串长度是多少呢？ 示例： 输入: words = [“time”, “me”, “bell”] 输出: 10 说明: 字符串S = “time#bell#” ， 提示： 1 <= words.length <= 2000 1 <= words[i].length <= 7 每个单词都是小写字母 。
变式2：利用字典树充分利用前缀(后缀)性质，优化暴力算法
【Leetcode_面试题_17_13】恢复空格 哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子”I reset the computer. It still didn’t boot!“已经变成了”iresetthecomputeritstilldidntboot”。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。 注意：本题相对原题稍作改动，只需返回未识别的字符数 示例： 输入： dictionary = [“looked”,“just”,“like”,“her”,“brother”] sentence = “jesslookedjustliketimherbrother” 输出： 7 解释： 断句后为”jess looked just like tim her brother”，共7个未识别字符。 提示：只包含26个小写字母
变式3：search方法的变异——match递归
Q：我知道match递归写法很妙，但有什么用呢？cur一条路走到黑的思路不是更好理解吗？
A：恰恰是因为“cur一条路走到黑”的思路有弊端——有时我们需要走一个分叉的路，去尝试更多的可能。
通过下面的两道变式题目，就能理解递归型search的强大之处
变式4：含有通配符的字典树匹配——递归的search
【Leetcode_211】添加与搜索单词-数据结构设计 设计一个支持以下两种操作的数据结构： void addWord(word) 添加单词 bool search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 ‘.’ 可以表示任何一个字母。
变式5：允许且必须变化一个字符后再匹配——递归的search
【Leetcode_676】实现一个魔法字典 实现一个带有buildDict, 以及 search方法的魔法字典。 对于buildDict方法，你将被给定一串不重复的单词来构建一个字典。 对于search方法，你将被给定一个单词，并且判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。
字典树（前缀树后缀树，单词查找树）其实早已融入了我们生活的点滴之中 ：
自动补全（输入法也是哦）
拼写检查与修复
IP 路由 (最长前缀匹配)
敏感词检测 面试/考试的时候很喜欢问一些关于搜索引擎的问题。这是一个经典问题，搜索引擎如何判断你搜索的内容是敏感词？
哦，我知道！是建立一个敏感词组成的Hash集合，将搜索内容利用分词库进行分词，分出的词去进行Hash匹配。 你获得了30分。
Hash的方法并不准确——“我爱日本”，分词出“我”，“爱”，“日本”，每个切片都毫无问题，组合在一起呢？
Hash的方法代价太高——为了解决上面的问题，只能把“我爱日本”作为一个整体加入哈希集合中。但是，你又需要把”我爱Japan”，“我爱JAPAN”，“我love日本”，”我love Japan”这样各种组合加入哈希集合，开销不可想象。 因此，海量敏感词的存储方式必然不是Hash，而是一个多叉的树形结构（比如Trie树）
☑ 部分题目来源 ：
结束了，不知道你意识到没有，Trie树的检索机制，和你的《英语词典》完全一致。 这是我想说的最后一个问题的答案——”字典树”名称的由来。
♬ END ♪ By a Lolicon ♥
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/196340.html原文链接：https://javaforall.cn
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/10727.html