[Java知识库]Java如何实现前缀树(对于存少量字符，如：小写字母字符)

实现难度：easy
建议：抄一遍，过程中注意我写的注释
实现算法模板

class Trie{
//内部类一个节点类
    class TrieNode{
        TrieNode[] nexts = new TrieNode[26];
        boolean last;
        int pass = 0;//用来记录通过节点的次数
        int end = 0;//用来标记作为结尾节点的次数
    }
    
 TrieNode root;//创建一个根节点
    public Trie(){
        root = new TrieNode();
    }

    public void insert(String word){
    if(word==null){return ;}
        TrieNode jump = root;
        jump.pass++;//给根节点++
        for(char c:word.toCharArray()){//把字符串打烂，并取出
            if(jump.nexts[c-'a']==null)jump.nexts[c-'a'] = new TrieNode();//c-‘a’使得你字符和索引有了关联。不同的索引值对应不同的指针，也就是说，转化成“每一个字符对应了一个指针”
            jump = jump.nexts[c-'a'];//跳动到下一位
              jump.pass++;
        }
        jump.last = true;
        jump.end++;//这里pass是每一次经过一个节点就++，而end是作为尾节点数量上当然少。根据数量可记忆pass应该在循环中变化
    }
    
    public int search(String word){
        if(word==null){return 0;}
         TrieNode jump = root;
        for(char c:word.toCharArray()){
            if(jump.nexts[c-'a']==null)return 0;//根据打烂的字符串，即所得字符，来找对应指针，如果找不到，当然直接结束。否则则继续向下跳
            jump = jump.nexts[c-'a'];
        }
        return jump.end;//因为此处找的是完整字符串，我们可以根据其尾节点的个数了解某一个字符串在该树中出现的次数
    }
    
    //点评：查找以某一个片段作为字符串而出现的个数，本质上讲和上面的search是一模一样，只不过我们现在是要的到“该片段字符的尾部字符，其所对应的节点中，了解到通过该节点的个数，即pass的数量”，
    public int startsWith(String prefix){
        if(prefix==null){return 0;}
        TrieNode jump = root;
        for(char c:prefix.toCharArray()){
            if(jump.nexts[c-'a']==null) return 0;
            jump = jump.nexts[c-'a'];//此处分析和search一样
        }
        return jump.pass;
    }
}

实战运用__剑指offer.62

class Trie{
    class TrieNode{
        TrieNode[] nexts = new TrieNode[26];
        boolean last;
    }
 TrieNode root;
    public Trie(){
        root = new TrieNode();
    }
    public void insert(String word){
        TrieNode jump = root;
        for(char c:word.toCharArray()){
            if(jump.nexts[c-'a']==null)jump.nexts[c-'a'] = new TrieNode();
            jump = jump.nexts[c-'a'];
        }
        jump.last = true;
    }
    public boolean search(String word){
         TrieNode jump = root;
        for(char c:word.toCharArray()){
            if(jump.nexts[c-'a']==null)return false;
            jump = jump.nexts[c-'a'];
        }
        return jump.last;
    }
    public boolean startsWith(String prefix){
        TrieNode jump = root;
        for(char c:prefix.toCharArray()){
            if(jump.nexts[c-'a']==null) return false;
            jump = jump.nexts[c-'a'];
        }
        return true;
    }
}