无锡论坛网站建设,烟台营销型网站建设,哪种浏览器什么网站都可以进,开发一个网站要学什么软件Day 67
题目描述 思路
初次思路#xff1a;此时还不了解什么是前缀树#xff0c;尝试自己实现一下 由于我们需要快速定位前缀和字符串#xff0c;于是我想到了使用hashset实现#xff0c;tes用于存放字符串#xff0c;prefixs存放前缀#xff0c;获取前缀通过使用subst…Day 67
题目描述 思路
初次思路此时还不了解什么是前缀树尝试自己实现一下 由于我们需要快速定位前缀和字符串于是我想到了使用hashset实现tes用于存放字符串prefixs存放前缀获取前缀通过使用substring进行拆分。
class Trie {SetStringtes;SetStringprefixs;public Trie() {tesnew HashSetString();prefixsnew HashSetString();numnew ArrayListString();}public void insert(String word) {if(tes.contains(word)){return;}else{tes.add(word);for(int i0;iword.length();i){String aword.substring(0,i);prefixs.add(a);}}}public boolean search(String word) {return tes.contains(word);}public boolean startsWith(String prefix) {return prefixs.contains(prefix);}
}/*** Your Trie object will be instantiated and called as such:* Trie obj new Trie();* obj.insert(word);* boolean param_2 obj.search(word);* boolean param_3 obj.startsWith(prefix);*/学习前缀树后 前缀树的作用在于快速检索字符串的前缀插入一个字符串即为从根一次插入孩子节点将字符串最后一个字符对应的节点标记结束节点再插入另外一个相同前缀但最后n个字符不一样的字符串那么在相同前缀的部分不需要插入新的节点直到第一个不同的字符添加一个新的子节点。 这样做的好处我们如果要获取两个字符串的前缀只需要从根节点向下遍历比较两个字符串只要到某个节点出现了分支则这个节点之前的节点就是两个字符的公共前缀。同时节约了存储空间 做法如下
class Trie {public Trie[]child;//孩子节点可能插入的是26个英文字母中的一个public boolean isend;//判断是否为一个字符串的结束 区分前缀和字符串public Trie() {childnew Trie[26];isendfalse;}public void insert(String word) {Trie nodethis;//根节点for(int i0;iword.length();i){char aword.charAt(i);int indexa-a;//转化为序号if(node.child[index]null){node.child[index]new Trie();//创建为新孩子}nodenode.child[index];//移动到下一个孩子}node.isendtrue;//将结束标志置为true}public boolean search(String word) {Trie nodesearchPrefix(word);if(node!nullnode.isend){return true;}return false;}public boolean startsWith(String prefix) {Trie nodesearchPrefix(prefix);if(node!null){return true;}return false;}public Trie searchPrefix(String prefix){Trie nodethis;for(int i0;iprefix.length();i){char aprefix.charAt(i);int indexa-a;if(node.child[index]null){//还没遍历完前缀就结束了 说明找不到return null;}nodenode.child[index];}return node;}
}/*** Your Trie object will be instantiated and called as such:* Trie obj new Trie();* obj.insert(word);* boolean param_2 obj.search(word);* boolean param_3 obj.startsWith(prefix);*/
