題意

Trie（發(fā)音類似 "try"）或者說 前綴樹 是一種樹形數(shù)據(jù)結(jié)構(gòu)川抡，用于高效地存儲(chǔ)和檢索字符串?dāng)?shù)據(jù)集中的鍵禾怠。這一數(shù)據(jù)結(jié)構(gòu)有相當(dāng)多的應(yīng)用情景莫湘，例如自動(dòng)補(bǔ)完和拼寫檢查倾鲫。

請(qǐng)你實(shí)現(xiàn) Trie 類：

Trie() 初始化前綴樹對(duì)象粗合。
void insert(String word) 向前綴樹中插入字符串 word。
boolean search(String word) 如果字符串 word 在前綴樹中乌昔，返回 true（即隙疚，在檢索之前已經(jīng)插入）；否則玫荣，返回 false甚淡。
boolean startsWith(String prefix) 如果之前已經(jīng)插入的字符串 word 的前綴之一為 prefix大诸，返回 true捅厂；否則，返回 false资柔。

分析

前綴樹是一種樹形結(jié)構(gòu)焙贷，其將一個(gè)字符串表示在一棵樹中，例如：

繪圖1.png

其中保存了數(shù)據(jù)【APP贿堰、APPLE辙芍、TIRE】其中，黃色節(jié)點(diǎn)表示含有這個(gè)對(duì)象，藍(lán)色表示只是路徑節(jié)點(diǎn)故硅。
注意：前綴樹是有一個(gè)總的虛擬頭節(jié)點(diǎn)庶灿。

題解

// 定義節(jié)點(diǎn)結(jié)構(gòu)
class TireNode {
    char value;// 當(dāng)前節(jié)點(diǎn)的值
    boolean isExists = false;// 當(dāng)前節(jié)點(diǎn)是都被包含【上述黃色節(jié)點(diǎn)】
    HashMap<Character, TireNode> children = new HashMap<Character, TireNode>();//【具體的分支】

    public TireNode(char value) {
        this.value = value;
    }
}
// 實(shí)現(xiàn)前綴樹
class Trie {
    // 虛擬頭節(jié)點(diǎn)
    TireNode dummyHead = new TireNode('-');

    public void insert(String word) {
        // 處理特殊情況
        if (word == null || word.length() == 0) return;
        // 是否需要?jiǎng)?chuàng)建根節(jié)點(diǎn)
        insertSub(word, 0, dummyHead.children);
    }

    // 將指定元素插入前綴樹的指定位置
    public void insertSub(String word, int start, HashMap<Character, TireNode> children) {
        // 插入到元素末尾，直接返回
        if (start == word.length()) return;

        if (children.containsKey(word.charAt(start))) {
            TireNode tireNodeTemp = children.get(word.charAt(start));
            // 判斷是否存在當(dāng)前元素
            if (start == word.length() - 1) tireNodeTemp.isExists = true;
            insertSub(word, start + 1, tireNodeTemp.children);
            // 不包含當(dāng)前節(jié)點(diǎn)
        } else {
            TireNode node = new TireNode(word.charAt(start));
            // 判斷是否存在當(dāng)前元素
            if (start == word.length() - 1) node.isExists = true;
            children.put(word.charAt(start), node);
            // 插入元素
            insertSub(word, start + 1, node.children);
        }
    }

     // 查找特定字符串
    public boolean search(String word) {
        TireNode tireNodeResult = searchSub(word, 0, dummyHead.children.get(word.charAt(0)));
        if (tireNodeResult == null) return false;
        return tireNodeResult.isExists;
    }


    public TireNode searchSub(String word, int start, TireNode tireNode) {
        if (tireNode == null) return null;
        if (tireNode.value == word.charAt(start)) {
            if (start == word.length() - 1) return tireNode;
            // 尋找下一個(gè)字符
            if (start + 1 < word.length())
                return searchSub(word, start + 1, tireNode.children.get(word.charAt(start + 1)));
        }
        return null;
    }

    // 是否有前綴
    public boolean startsWith(String prefix) {
        TireNode tireNodeResult = searchSub(prefix, 0, dummyHead.children.get(prefix.charAt(0)));
        if (tireNodeResult == null) return false;
        return true;
    }

}