前言本次分享的Trie字典树是数据结构专题的一个分支。理解Trie树这种树型数据结构，对于构建算法知识体系和数据结构的帮助是很有帮助的。我对Trie树的理解：将字符串拼接在一起，消除不必要的存储，使用的是字符串的公共前缀。其实对于它的理解，理解了这句话，就可以利用字符串的公共前缀来减少查询时间，尽量减少不必要的字符串比较，查询效率比哈希树要高。如果你不知道什么是Trie数据结构，或者知道一些，但是它是如何实现一个简单的Trie树的，那么这篇文章可能适合你阅读。然后围绕以下几点介绍Trie树👇基本概念基本属性应用场景2例子基本概念首先我们要对Trie树做一些基本的了解。Trie树中文叫字典树、前缀树等，以后我就叫它字典树。我们来看看维基百科对它的描述??在计算机科学中，trie，也称为前缀树或字典树，是一种有序树，用于存储关联数组，其中的键通常是字符串。与二叉搜索树不同的是，键不直接存储在节点中，而是由节点在树中的位置决定。一个节点的所有后代都有相同的前缀，就是这个节点对应的字符串，根节点对应的是空字符串。一般来说，并不是所有的节点都有对应的值，只有叶子节点对应的键和一些内部节点有相关的值。朴实无华的描述，其实我们看一张图就明白了~，网上找了一张不错的图，具体出处，这里就不加了，因为找不到原作者~字典树形图1这里需要说明的是，一般来说应该用一个点来表示一个字符。这里为了更好的解释，我只是用边来描述字符。可以发现，这棵字典树用边来表示字母，从根节点到树上某个节点的路径表示一个字符串。比如1→2→6代表字符串aba。再比如，1→4→8组成的字符串是ca，那么我们往下展开，有没有caa，cab，那么它们都会经过1→4→8，这些路径说明它们有一个共同的prefix的前缀，这个前缀的内容是ca。说到这里，我们知道字典树是利用字符串的前缀来解决问题的。那么它的具体属性有哪些呢，下面就来介绍一下~基本属性对上面的概念有了一定的了解之后，接下来我们来看一下Trie树的基本属性。据此大致可以分为三点：👇根节点不包含字符，每个节点除根节点外只包含一个字符。从根节点到某个节点，将路径上传递的字符连接起来，形成该节点对应的字符串。每个节点的所有子节点包含不同的字符串。接下来我们稍微分析一下，可以结合一张图来看👇我们通过how,hi,her,hello,so,see这六个字符串来构建它，如下图所示。图解Trie树的第一个属性：从图中也可以看出，根节点为/，代表的内容为空。其他节点，比如根节点的下一级，有h和s，代表两个字符。第二个性质：从根节点到某个节点，将路径上传递的字符连接起来，形成该节点对应的字符串。比如how代表一个字符串，hi也代表一个字符串，但是你有没有想过为什么he和hel不能代表一个字符串？当你想到这个的时候，就说明你已经很仔细的阅读了，我们很快就会掌握的。确实，从图中我们会发现，有些节点的颜色是不一样的。这是因为我们已经计划用这个暗节点来表示一个字符串的结尾。想一想，像这样子的作用是什么？那么在实际的代码中，我们应该如何约定或者做标记呢？其实我们只需要设置一个标志位即可。例如，下面的👇constTrieNode=function(){this.next=Object.create(null)this.isEnd=false};当前isEnd变量表示当前节点是否为结束字符串，当isEnd为True时，表示从根节点到该字符，形成的字符串存在，是一个完整的字符串。第三个属性：每个节点的所有子节点包含不同的字符串。显然，我们从根节点开始，依次往下走，会发现每个节点下面的节点都不一样，所以依次形成的字符串不可能相同。应用场景当我们对Trie树有了一定的了解之后，我们就可以看到它有哪些实际的应用场景了。这里参考的是网上提供的几点👇在搜索引擎关键词提示中，引擎会自动弹出匹配关键词的下拉框，这个应用场景大家应该不陌生。如何使用高效的数据结构来存储下拉框？这符合字典树的性质，因此可以利用字典树来构造特定的数据，以达到更快的检索效果。字符串检索是将一些字符串（字典）的已知信息预先保存在trie树中，查找其他未知字符串是否出现过或出现频率。可以用一个例子来说明情况👇1000万个字符串，其中有一些是重复的，需要把重复的全部去掉，没有重复的字符串要保留。给定一个由N个单词组成的熟悉单词列表，以及一篇用全小写英文写成的文章，请按照最早出现的顺序写下所有不在熟悉单词列表中的新单词。词频统计给定一个很长的字符串，统计出现频率最高的字符串。比如有一个1G大小的文件，里面每一行都是一个word。字的大小不超过16字节，内存限制大小为1M。返回100个最常用的单词。一个文本文件大约有10000行，每行一个词，要求统计出现次数最多的前10个词。请给出你的想法和时间复杂度分析。字符串的最长公共前缀现在，我们应该知道Trie树是使用多个字符串的公共前缀来节省存储空间的。当我们在一棵trie树中存储大量的字符串时，我们可以很快的得到一些字符字符串的公共前缀，所以可以利用这个特性来解决一些前缀问题。如果非要举个例子，那就有例子👇给定N个小写英文字母字符串和Q个查询，即问某两个字??符串的最长公共前缀的长度是多少？应用场景还有很多，剩下的可以自己去探索。接下来，我们来看一下实际题目，如何构造字典树~2个例子接下来，我们以两个题目为例，看看字典树在实际应用中是如何使用的。解决了什么问题👇字典中最长的单词?链接：字典中最长的单词给出了一个由字符串数组单词组成的英文字典。从中找出最长的单词，它是由单词词典中的其他单词逐渐添加一个字母组成的。如果有多个可行答案，则返回答案中字典顺序最小的单词。如果没有答案，则返回一个空字符串。示例1：输入：words=["w","wo","wor","worl","world"]输出："world"解释：单词"world"可以由"w","wo","wor",和"worl"添加一个字母。示例2：输入：words=["a","banana","app","appl","ap","apply","apple"]输出："apple"解释："apply"和"apple"可以由字典中的单词组成。但是“apple”在词典编排上比“apply”少。提示：这道题无非就是找最长的单词，可以拆分到words数组的某一部分。最暴力的想法就是枚举每一项，但是这样做的时间复杂度是巨大的。这时候，我们能不能想一想，这个问题的共同特点是什么？是的，前缀是一样的。从这个角度来看，是否可以用这棵前缀树来存储它的数据，然后遍历字典树，只要这棵树只有一个分支，就说明它有解，如果有两个以上的分支，没有答案。复杂度分析应该很好理解，这里略过。在这里，我的解决方案是构造一个字典树。当然还有其他的解决方案，这里就不展开了。大家可以看一下我的代码~最长的一串代码点在这里??其实你会发现如果构造一颗Trie树，它会消耗大量的空间，也就是用空间换取时间，所以需要根据实际问题解决。ImplementTrie(prefixtree)??链接：implementTrie(prefixtree)实现一个Trie（前缀树），包括insert、search、startsWith这三个操作。示例：Trietrie=newTrie();trie.insert("apple");trie.search("apple");//返回truetrie.search("app");//返回falsetrie.startsWith("app");//returntruetrie.insert("app");trie.search("app");//returntrue解释：你可以假设所有的输入都是由小写字母a-z组成的。所有输入都保证是非空字符串。本题是典型的写Trie树。第一次写这个题目，如果没有思路，可以尝试先看看别人的代码，看看基本套路在哪里。话不多说，大家可以参考这段代码看看如何构造字典树#128071;leetcode-在这里实现Trie树代码点??剩下的删除操作，以及出现频率的统计字符串，你自己实现吧。基本上不难。画个图就知道怎么实现了~话题无穷无尽。学完这些话题，希望大家对字典树Trie有更好的了解，对它有更深的认识。明白了~，接下来我准备了四套题，希望对你有所帮助~字典最长词实现Trie（前缀树）查词II加载题
