字典樹Trie

字典樹也叫前綴樹，是一種在字符串查找，前綴匹配等問題廣泛應(yīng)用的算法，為什么使用字典樹呢？我們都知道如果對于一個存儲有n個條目的數(shù)據(jù)集做查詢，線性結(jié)構(gòu)的時間復(fù)雜度是O(n)，這是相當(dāng)恐怖的，改進(jìn)的基于紅黑樹的查詢時間復(fù)雜度是O(logn)，雖然已經(jīng)好很多，但是當(dāng)n非常大時，這個時間復(fù)雜度還是不能接受的。而字典樹能做到查詢的時間復(fù)雜度和數(shù)據(jù)集存儲的數(shù)目n無關(guān)，而僅和被查詢的字符串長度有關(guān)，所以它在查找時只有O(1)的時間復(fù)雜度。這是怎么做到的呢，其實很簡單，下圖是某存儲英文的字典樹的結(jié)構(gòu)：

Trie

該樹中存儲了英語單詞，如果要查詢某個單詞，比如，只需要先找到w，再找到i、n、d即可?？梢妼γ總€單詞的查找只需要查找單詞長度次，而且每次查找只需查找26次之內(nèi)（即便算上大寫也在52次之內(nèi)）。
Trie數(shù)據(jù)結(jié)構(gòu)設(shè)計要點：

• 添加操作：從根開始向下，如果某個節(jié)點沒有則拓展一個新節(jié)點，添加完畢后在最后一個節(jié)點處將標(biāo)志置true；
• 查詢操作：基本過程與插入相同，向下查找，如果中間遇到一次節(jié)點不存在，直接返回false，一直向下查找，最終返回標(biāo)志位；
• 每遍歷到一個葉子節(jié)點，就查到一個單詞（條目）；
• 可能某個單詞是其它單詞的前綴，如果沒到葉子節(jié)點就存儲了一個單詞，則將此處標(biāo)志置true。

字典樹的實現(xiàn)
首先考慮節(jié)點結(jié)構(gòu)，并假設(shè)這里的節(jié)點僅存儲小寫英文單詞，故每個節(jié)點下應(yīng)該有26個分支（實際如何存儲根據(jù)具體情境）：

class Node{
    char c;
    Node next[26];//指向下一個節(jié)點
}

不過由于在尋找下一個節(jié)點時，我們實際上已經(jīng)知道了要找哪個，故可以將當(dāng)前節(jié)點和和其指向的節(jié)點存儲為一個整體（相當(dāng)于存儲是在邊上），故節(jié)點設(shè)計為：

class Node{
    boolean isWord;
    Map<char,Node> next;
}

其中isWord用于標(biāo)識單詞結(jié)尾，從而Trie類：

import java.util.TreeMap;
public class Trie {//不需要泛型，這里僅解決字符串類問題
    private class Node{//Trie的節(jié)點類
        public boolean isWord;
        public TreeMap<Character,Node> next;

        public Node(boolean isWord){
            this.isWord = isWord;
            next = new TreeMap<>();
        }
        public Node(){
            this(false);//表示使用上面的構(gòu)造函數(shù)
        }
    }

    private Node root;
    private int size;

    public Trie(){
        root = new Node();
        size = 0;
    }

    //獲取Trie中的單詞數(shù)量
    public int getSize(){
        return size;
    }
    //向Trie中添加新單詞(字符串)
    public void add(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (cur.next.get(c) == null)//如果映射中沒有包含到c的映射
                cur.next.put(c, new Node());
            cur = cur.next.get(c);
        }
        if (!cur.isWord) {//首先檢查該單詞是否已經(jīng)存在
            cur.isWord = true;
            //此時來到了當(dāng)前添加單詞的最后節(jié)點，但不一定是葉子節(jié)點，因為可能是別的單詞前綴
            size++;
        }
    }//作業(yè)：使用遞歸寫法完成添加操作

    public boolean contains(String word){
        //查詢單詞word是否在Trie中
        Node cur = root;
        for(int i=0;i<word.length();i++){
            char c = word.charAt(i);
            if(cur.next.get(c) == null)
                return false;
            cur = cur.next.get(c);
        }
        return cur.isWord;
    }//作業(yè)，遞歸寫法

    //其實Trie也是一個集合
    public boolean isPrefix(String prefix){
        //查詢Trie中是否有單詞以prefix為前綴(一個單詞也是本身的前綴)
        Node cur = root;
        for(int i=0;i<prefix.length();i++){
            char c = prefix.charAt(i);
            if(cur.next.get(c) == null)
                return false;
            cur = cur.next.get(c);
        }
        return true;//和查詢單詞操作類似，不過無需檢查是否包含單詞
        //作業(yè)：BSTSet中查詢前綴
    }
}

可以看到，Trie類的實現(xiàn)我們借助了TreeMap等底層數(shù)據(jù)結(jié)構(gòu)，這正是數(shù)據(jù)結(jié)構(gòu)的魅力，就像樂高積木一樣，由一些基礎(chǔ)的木塊一步步搭建出美麗的藝術(shù)品。

Trie的應(yīng)用——LeetCode207、211

LeetCode207不再介紹，就是設(shè)計一個字典樹類，支持添加和查找操作，上面實現(xiàn)的類修改下類名即可。
LeetCode211

LeetCode211

這個題目其實和Trie類要完成的工作類似，不過加入了一些更靈活的條件（簡易正則表達(dá)式），只需對我們的Trie類做小部分修改即可：

import java.util.TreeMap;
class WordDictionary {
    private class Node{//Trie的節(jié)點類
        public boolean isWord;
        public TreeMap<Character,Node> next;

        public Node(boolean isWord){
            this.isWord = isWord;
            next = new TreeMap<>();
        }
        public Node(){
            this(false);//表示使用上面的構(gòu)造函數(shù)
        }
    }
    private Node root;
    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new Node();
    }
    public void addWord(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (cur.next.get(c) == null)//如果映射中沒有包含到c的映射
                cur.next.put(c, new Node());
            cur = cur.next.get(c);
        }
        if (!cur.isWord) //首先檢查該單詞是否已經(jīng)存在
            cur.isWord = true;
    }
    public boolean search(String word) {
        return match(root, word,0);
    }
    private boolean match(Node node, String word, int index) {
        //從index處開始匹配
        if (index == word.length())
            return node.isWord;//遞歸終止條件,word匹配完畢,若為true則返回匹配成功,false匹配失敗
        char c = word.charAt(index);
        if (c == '.') {
            for (char nextChar : node.next.keySet()) {//是.則遍歷所有字母
                if (match(node.next.get(nextChar), word, index + 1))
                    return true;
            }
            return false;
        } else {
            if (node.next.get(c) == null)
                return false;
            return match(node.next.get(c), word, index + 1);//繼續(xù)匹配后面的部分
        }
    }
}

可以發(fā)現(xiàn)，我們只對查詢函數(shù)做了改動，而查詢主要是基于遞歸實現(xiàn)的。