力扣面试150题--实现Trie（前缀树）

Day 67

题目描述

思路

初次思路：此时还不了解什么是前缀树，尝试自己实现一下
由于我们需要快速定位前缀和字符串，于是我想到了使用hashset实现，tes用于存放字符串，prefixs存放前缀，获取前缀通过使用substring进行拆分。

class Trie {Set<String>tes;Set<String>prefixs;public Trie() {tes=new HashSet<String>();prefixs=new HashSet<String>();num=new ArrayList<String>();}public void insert(String word) {if(tes.contains(word)){return;}else{tes.add(word);for(int i=0;i<=word.length();i++){String a=word.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() {child=new Trie[26];isend=false;}public void insert(String word) {Trie node=this;//根节点for(int i=0;i<word.length();i++){char a=word.charAt(i);int index=a-'a';//转化为序号if(node.child[index]==null){node.child[index]=new Trie();//创建为新孩子}node=node.child[index];//移动到下一个孩子}node.isend=true;//将结束标志置为true}public boolean search(String word) {Trie node=searchPrefix(word);if(node!=null&&node.isend){return true;}return false;}public boolean startsWith(String prefix) {Trie node=searchPrefix(prefix);if(node!=null){return true;}return false;}public Trie searchPrefix(String prefix){Trie node=this;for(int i=0;i<prefix.length();i++){char a=prefix.charAt(i);int index=a-'a';if(node.child[index]==null){//还没遍历完前缀就结束了 说明找不到return null;}node=node.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);*/