目录Trie树，即词典树，又称前缀树，是一种树状结构。典型应用用于对大量字符串（但不限于字符串）进行统计和排序，因此常被搜索引擎用于文本词频统计。它的首要任务是尽量减少不必要的字符串比较并提高搜索效率。Trie的核心思想是以空间换取时间，利用字符串的公共前缀来减少查询时间的开销，达到提高效率的目的。根节点的基本性质是不包含字符，除根节点外的每个节点只包含一个字符。从根节点到某个节点，路径上传递的字符是相连的，该节点对应的字符串在每个节点的所有子节点中包含不同的字符实际应用，比如搜索720.字典中最长的单词（easy）给出了一个由字符串数组单词组成的英文字典。返回通过从单词词典中的其他单词递增添加字母而形成的单词中最长的单词。如果有多个可行答案，则返回答案中字典顺序最小的单词。如果没有答案，则返回一个空字符串。示例1：输入：words=["w","wo","wor","worl","world"]输出："world"解释：单词"world"可以由"w","wo"组成"、"wor"和"world"逐渐添加一个字母。示例2：输入：words=["a","banana","app","appl","ap","apply","apple"]输出："apple"解释："apply"和"apple"可以由字典中的单词组成。但是“apple”的字典序小于“apply”提示：1<=words.length<=10001<=words[i].length<=30所有输入的字符串words[i]只包含小写字母。方法一：sort+hash思路：对数组进行排序，然后遍历字符串数组，判断数组中每个字符串的子串是否在数组中。复杂度：时间复杂度O(mn)，m为字符串数组长度，n为字符串的最大长度。空间复杂度O(m)js:varlongestWord=function(words){letset=newSet()words.forEach(v=>set.add(v))//set好找//先按长度排序,按字典顺序words.sort((a,b)=>a.length===b.length?a.localeCompare(b):b.length-a.length)for(leti=0;i{//将所有字符串插入trietrie.insert(word)})letres=''const_helper=(nodes,path)=>{if(path.length>res.length||(res.length===path.length&&res>path)){res=path}//{a:{b1:{c1:{isEnd:true}},b2:{c2:{isEnd:true}}}}for(const[key,value]ofObject.entries(nodes)){if(value.isEnd){//如果当前字符它是一个字符串的结尾path+=key_helper(value,path)//递归查找path=path.slice(0,-1)//回溯}}}_helper(trie.children,'')//递归查找最大长度的单词returnres}varTrie=function(){this.children={};};Trie.prototype.insert=function(word){letnodes=this.children;for(constchofword){//循环单词if(!nodes[ch]){//当前字符不在子节点中，则创建子节点到子节点的响应位置[ch]={};}nodes=nodes[ch];//将指针移动到下一个字符}nodes.isEnd=true;//字符是否结束};212.WordSearchII(hard)给出一本由字符串数组组成的英文书wordsdictionary返回words中最长的单词，它是由words字典中其他单词的字母递增组成的。如果有多个可行答案，则返回答案中字典顺序最小的单词。如果没有答案，则返回一个空字符串。示例1：输入：words=["w","wo","wor","worl","world"]输出："world"解释：单词"world"可以由"w","wo"组成"、"wor"和"world"逐渐添加一个字母。示例2：输入：words=["a","banana","app","appl","ap","apply","apple"]输出："apple"解释："apply"和"apple"可以由字典中的单词组成。但是“apple”的字典序小于“apply”提示：1<=words.length<=10001<=words[i].length<=30所有输入的字符串words[i]只包含小写字母。思路：将words数组中的所有字符串加入到Trie中，然后遍历格子，判断格子路径形成的字符串是否在Trie中，然后继续向上、下、左、右四个方向回溯正确的。复杂度分析：时间复杂度O(MN?3^L)，空间复杂度O(max(MN,KL))，访问空间O(MN)，字典树O(KL)，L为最长字符的长度字符串，K是单词数组的长度。dfs递归栈的最大深度为O(min(L,MN))，方法1.TrieJs:varfindWords=function(board,words){consttrie=newTrie();constdxys=[[0,-1],[-1,0],[0,1],[1,0],];constxLen=board.length,yLen=board[0].length;常量访问={};constret=[];//构建Triefor(letwordofwords){trie.insert(word);}//DFSboardconstdfs=(x,y,nodes,str)=>{if(nodes[board[x][y]].isEnd){ret.push(str+board[x][y]);//设置为false以防止重复添加字符串到retnodes[board[x][y]].isEnd=false;}//处理这一层的状态nodes=nodes[board[x][y]];str+=棋盘[x][y]；//在访问过的四个链接的方向上检索[x*100+y]=true;for(let[dx,dy]ofdxys){constnewX=x+dx,newY=y+dy;如果(newX<0||newY<0||newX>=xLen||newY>=yLen||!nodes[板[newX][newY]]||已访问[newX*100+newY])继续；dfs(newX,newY,节点,海峡);}访问过[x*100+y]=false；};for(letx=0;x思路：本题字符集长度为26，即26个小写英文字母，isEnd表示该节点是否为字符串结尾。插入字符串：从字段树的根节点开始，如果子节点存在，则继续处理下一个字符，如果子节点不存在，则创建子节点到children的对应位置，继续沿指针，并处理下一个字符一个字符，以插入'cad'为例查找前缀：从根节点开始，如果子节点存在，则沿着指针继续查找下一个子节点，直到最后一个，如果前缀的所有字符都被找到，则说明字典树中包含前缀。如果子节点不存在，则表示字典树不包含该前缀，返回false。查找字符串：与查找前缀相同，只是最后返回的节点的isEnd为true，这意味着该字符串只是字典树的一个分支。复杂度分析：时间复杂度，初始化为O(1)，其余操作均为O(S)，s为字符串长度。空间复杂度为O(T)，T为字符集的大小。这道题是26js:varTrie=function(){this.children={};};Trie.prototype.insert=function(word){letnodes=this.children;for(constchofword){//循环单词if(!nodes[ch]){//当前字符不在子节点中，创建子节点到子节点的响应位置[ch]={};}nodes=nodes[ch];//将指针移动到下一个字符子节点}nodes.isEnd=true;//字符是否结束};Trie.prototype.searchPrefix=function(prefix){letnodes=this.孩子们;for(constchofprefix){//循环前缀if(!nodes[ch]){//当前字符不在子节点中，直接返回falsereturnfalse;}nodes=nodes[ch];//将指针移动到下一个A字符子节点}returnnodes;//返回最后一个节点}Trie.prototype.search=function(word){constnodes=this.searchPrefix(word);//判断searchPrefix返回的节点是否为字符串结尾字符（字首）;};视频讲解：传送门
