字典樹(shù)(trie)

在leetcode 上刷題遇到的一種數(shù)據(jù)結(jié)構(gòu)，以前沒(méi)聽(tīng)說(shuō)過(guò)，怪我孤陋寡聞，經(jīng)過(guò)了解發(fā)現(xiàn)應(yīng)用還是很廣的。覺(jué)得有必要記錄下

<a > leetcode 208</a>
<a >Trie的維基百科介紹</a>

• 概念
• 根節(jié)點(diǎn)不包含字符串
• 從根節(jié)點(diǎn)到某一葉子節(jié)點(diǎn)，路徑上組成的所有字符就是該節(jié)點(diǎn)對(duì)應(yīng)的字符串
• 每個(gè)節(jié)點(diǎn)的公共前綴作為一個(gè)字符節(jié)點(diǎn)保存
• 應(yīng)用
• 詞頻統(tǒng)計(jì)：比hash或者堆要節(jié)省空間，
• 前綴匹配：前綴匹配的算法復(fù)雜度是O(1)， 要查找匹配前綴字符串的長(zhǎng)度

實(shí)現(xiàn)

class TrieNode{
    TrieNode[] childs = new TrieNode[26]; // a-z
    int count; //frequence;
    char prefix; //當(dāng)前節(jié)點(diǎn)的字符前綴
    public TrieNode(char prefix){
        this.prefix = prefix; 
        count = 1; //root 的count 初始化為0，所以要
    }
    public TrieNode(){}
    public void addCount(){
        this.count++;
    }
    public void setPrefix(char prefix){
        this.prefix = prefix;
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
         root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode searchNode = root;
        for (int level = 0;level < word.length();level++){
            char currentChar = word.charAt(level);
            TrieNode node = searchNode.childs[currentChar-'a'];
            if (searchNode.childs[currentChar-'a'] == null)      //如果這個(gè)前綴的還是null，那么新建插入一個(gè)
                searchNode.childs[currentChar-'a'] = new TrieNode(currentChar);
            else
                node.count++;
            searchNode = searchNode.childs[currentChar-'a'];
        }
    }

    public boolean search(String word) {
        TrieNode searchNode = root;
        for (int level = 0;level < word.length();level++){
            char currentChar = word.charAt(level);
            TrieNode node = searchNode.childs[currentChar-'a'];
            if (node == null)
                return false;
            searchNode = node;
        }
        int childCount = 0;
        for (TrieNode trieNode : searchNode.childs){
            if (trieNode == null)
                continue;
            childCount += trieNode.count;
        }
        return searchNode.count > childCount;
    }


    public boolean startsWith(String prefix) {
        TrieNode searchNode = root;
        for (int level = 0;level < prefix.length();level++){
            char currentChar = prefix.charAt(level);
            TrieNode node = searchNode.childs[currentChar-'a'];
            if (node == null)
                return false;
            searchNode = node;
        }
        return true;
    }
}