Leetcode hot100 实现 Trie (前缀树)【中等】

特点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){ nodenode.nextNode[c-a]; //2-2、没有的插进去 }else{ node.nextNode[c-a]new Trie(); nodenode.nextNode[c-a]; } } //3、处理词尾节点 node.isEndtrue; } /** 比如前缀树里已经有单词apple这里需要考虑4种情况 1apple:true 2) app:false 3) applee:flase 4bananafalse */ public boolean search(String word) { //1.先拿到this根节点 Trie node this; //2. for(char c: word.toCharArray()){ if(node.nextNode[c-a]!null){ nodenode.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){ nodenode.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); */