?LeetCode刷題實(shí)戰(zhàn)208：實(shí)現(xiàn) Trie (前綴樹)

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app"); 
trie.search("app"); // 返回 true

說明:

你可以假設(shè)所有的輸入都是由小寫字母 a-z 構(gòu)成的。
保證所有輸入均為非空字符串。

class Trie {
    /**
     * 當(dāng)前節(jié)點(diǎn)的值
     */
    public char value;
    /**
     * a-z有26個(gè)字母，需要訪問時(shí)由于a的ASCII碼為97，所以所有字母訪問的對(duì)應(yīng)下表皆為 字母的ASCII碼-97
     */
    public Trie[] children=new Trie[26];
    /**
     * 標(biāo)識(shí)此節(jié)點(diǎn)是否為某個(gè)單詞的結(jié)束節(jié)點(diǎn)
     */
    public boolean endAsWord=false;
    
    public Trie() {
        
    }
    /**
     * 插入一個(gè)單詞
     * @param word 單詞
     */
    public void insert(String word) {
        if(word!=null){
            //分解成字符數(shù)組
            char[] charArr=word.toCharArray();
            //模擬指針操作,記錄當(dāng)前訪問到的樹的節(jié)點(diǎn)
            Trie currentNode=this;
            for(int i=0;i<charArr.length;i++){
                char currentChar=charArr[i];
                //根據(jù)字符獲取對(duì)應(yīng)的子節(jié)點(diǎn)
                Trie node=currentNode.children[currentChar-97];
                if(node!=null && node.value==currentChar){//判斷節(jié)點(diǎn)是否存在
                   currentNode=node;
                }else{//不存在則創(chuàng)建一個(gè)新的葉子節(jié)點(diǎn),并指向當(dāng)前的葉子節(jié)點(diǎn)
                    node=new Trie();
                    node.value=currentChar;
                    currentNode.children[currentChar-97]=node;
                    currentNode=node;
                }
            }
            //這個(gè)標(biāo)識(shí)很重要
            currentNode.endAsWord=true;
        }
    }
    /**
     * 檢索指定單詞是否在樹中
     * @param word 單詞
     */
    public boolean search(String word) {
        boolean result=true;
        if(word!=null && !word.trim().equals("")){
            char[] prefixChar=word.toCharArray();
            Trie currentNode=this;
            for(int i=0;i<prefixChar.length;i++){
                char currentChar=prefixChar[i];
                Trie node=currentNode.children[currentChar-97];
                if(node!=null && node.value==currentChar){//判斷節(jié)點(diǎn)是否存在
                   currentNode=node;
                }else{
                    result=false;
                    break;
                }
            }
            if(result){
                result=currentNode.endAsWord;
            }
        }
        return result;
    }
    /**
     * 檢索指定前綴是否在樹中
     * @param word 單詞
     */
    public boolean startsWith(String prefix) {
        boolean result=true;
        if(prefix!=null && !prefix.trim().equals("")){
            char[] prefixChar=prefix.toCharArray();
            Trie currentNode=this;
            for(int i=0;i<prefixChar.length;i++){
                char currentChar=prefixChar[i];
                Trie node=currentNode.children[currentChar-97];
                if(node!=null && node.value==currentChar){//判斷節(jié)點(diǎn)是否存在
                    currentNode=node;
                }else{
                    result=false;
                    break;
                }
            }
        }
        return result;
    }
}