赞
踩
在计算机科学中,trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。Trie这个术语来自于retrieval(检索)。根据词源学,trie的发明者Edward Fredkin把它读作/ˈtriː/ “tree”。但是,其他作者把它读作/ˈtraɪ/ “try”。
trie中的键通常是字符串,但也可以是其它的结构。trie的算法可以很容易地修改为处理其它结构的有序序列,比如一串数字或者形状的排列。比如,bitwise trie中的键是一串比特,可以用于表示整数或者内存地址。
比如有四个单词:app、apple、bit、cat,根据他们构建字典树如下:
力扣208. 实现 Trie (前缀树)
Trie(发音类似 “try”)或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。请你实现 Trie 类:
Trie代码实现中主要涉及四个内容:
class Trie { // 存储孩子节点 Trie[] children; // 标记该节点是否为终止节点 boolean isEnd; public Trie() { // 初始化 children=new Trie[26]; } // 数据插入操作 public void insert(String word) { // 当前根节点 Trie cur=this; // 当前根节点的孩子节点 Trie[] branches=cur.children; char[] chs=word.toCharArray(); // 依次遍历当前单词的所有字符 for(int i=0;i<chs.length;i++){ // int index=chs[i]-'a'; // if(branches[index]!=null){ // cur=branches[index]; // branches=cur.children; // }else{ // 说明该字符已经存在 // branches[index]=new Trie(); // cur=branches[index]; // branches=cur.children; // } // 确定孩子节点的位置 int index=chs[i]-'a'; // 说明该字符不存在,则对该孩子节点进行初始化 if(branches[index]==null){ branches[index]=new Trie(); } // 调整当前根节点为该孩子节点 cur=branches[index]; branches=cur.children; } // 单词遍历结束,此时cur指向该单词最后一个字符所在节点,将其标记为终止节点 cur.isEnd=true; } // public boolean search(String word) { // 当前根节点 Trie cur=this; Trie[] branches=children; char[] chs=word.toCharArray(); for(int i=0;i<chs.length;i++){ int index=chs[i]-'a'; // 如果该字符存在,则一直向下搜索,直到遍历完整个单词 if(branches[index]!=null){ cur=branches[index]; branches=cur.children; }else{ // 说明该字符不存在 return false; } } // 此时cur指向单词的最后一个字符对应的节点,如果该节点是终止节点则说明该单词存在 return cur.isEnd; } public boolean startsWith(String prefix) { // 当前根节点 Trie cur=this; Trie[] branches=cur.children; char[] chs=prefix.toCharArray(); for(int i=0;i<chs.length;i++){ int index=chs[i]-'a'; // 说明该字符已经存在 if(branches[index]!=null){ cur=branches[index]; branches=cur.children; }else{ return false; } } // 此时cur指向单词的最后一个字符对应的节点,说明整个字符串都存在,也就是以该字符串开头的单词都存在 return true; } }
class Trie { HashMap<Character,Trie> children; boolean isEnd; String value; public Trie() { children=new HashMap<>(); } public void insert(String word) { Trie cur=this; HashMap<Character,Trie> branches=cur.children; char[] chs=word.toCharArray(); for(int i=0;i<chs.length;i++){ if(!branches.containsKey(chs[i])){ branches.put(chs[i],new Trie()); } cur=branches.get(chs[i]); branches=cur.children; } cur.isEnd=true; cur.value=word; } public boolean search(String word) { Trie cur=this; HashMap<Character,Trie> branches=cur.children; char[] chs=word.toCharArray(); for(int i=0;i<chs.length;i++){ if(branches.containsKey(chs[i])){ cur=branches.get(chs[i]); branches=cur.children; }else{ return false; } } return cur.isEnd; } public boolean startsWith(String prefix) { Trie cur=this; HashMap<Character,Trie> branches=cur.children; char[] chs=prefix.toCharArray(); for(int i=0;i<chs.length;i++){ if(branches.containsKey(chs[i])){ cur=branches.get(chs[i]); branches=cur.children; }else{ return false; } } return true; } }
参考资料:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。