【中等】)
特点：
1、多叉树
2、主要用到这三个方法：插入、查找、前缀匹配。没有更新和删除哈
3、每个节点都要维护26个字母的空间，整棵树摞起来，其实空间消耗蛮大的。但我们建立前缀树的目的不就是空间换时间嘛！
class Trie { boolean isEnd; //惰性值是false，所以只需要确认是词尾节点时手动赋值true，除了词尾节点其他new的Trie啥都不用管。 Trie[] nextNode = new Trie[26]; //下标对应字母，存的内容是子节点 public Trie() { } public void insert(String word) { //1.先拿到this根节点 Trie node = this; for (char c: word.toCharArray()){ //2-1、前缀树里已经有的 if(node.nextNode[c-'a']!=null){ node=node.nextNode[c-'a']; //2-2、没有的插进去 }else{ node.nextNode[c-'a']=new Trie(); node=node.nextNode[c-'a']; } } //3、处理词尾节点 node.isEnd=true; } /** 比如前缀树里已经有单词apple，这里需要考虑4种情况 1）apple:true 2) app:false 3) applee:flase 4）banana：false */ public boolean search(String word) { //1.先拿到this根节点 Trie node = this; //2. for(char c: word.toCharArray()){ if(node.nextNode[c-'a']!=null){ node=node.nextNode[c-'a']; }else return false; //针对情况3和情况4 } //3.妙！ 覆盖情况1和情况2 return node.isEnd; } public boolean startsWith(String prefix) { //1.先拿到this根节点 Trie node = this; //2. for(char c: prefix.toCharArray()){ if(node.nextNode[c-'a']!=null){ node=node.nextNode[c-'a']; }else return false; } //3.走到最后了 return true; } } /** * 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); */
