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

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

• Trie() 初始化前綴樹(shù)對(duì)象。
• void insert(String word) 向前綴樹(shù)中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前綴樹(shù)中，返回 true（即，在檢索之前已經(jīng)插入）；否則，返回 false 。
• boolean startsWith(String prefix) 如果之前已經(jīng)插入的字符串 word 的前綴之一為 prefix ，返回 true ；否則，返回 false 。

type Trie struct {
    isEnd bool //是否為一個(gè)單詞的結(jié)束
    next [26]*Trie //保存下一個(gè)字符的26種可能;next數(shù)組保存了當(dāng)前字符的下一個(gè)字符節(jié)點(diǎn)數(shù)組
}


/** Initialize your data structure here. */
func Constructor() Trie {
    return Trie{}
}


/** Inserts a word into the trie. */
func (this *Trie) Insert(word string)  {
    node := this
    //遍歷單詞的每個(gè)字符,判斷字符所在的索引位置是否有值，有值則繼續(xù)遍歷，沒(méi)有則創(chuàng)建一個(gè)新的節(jié)點(diǎn)
    for _, char := range word {
        index = char - 'a'
        if node.next[index] == nil {
            node.next[index] = &Trie{}
        }
        node = node.next[index]
    }
    node.isEnd = true //遍歷到最后設(shè)置為true
}


/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
    node := this
    for _, char := range word {
        index = char - 'a'
        if node.next[index] == nil {
            node.next[index] = &Trie{}
        }
        node = node.next[index]
    }
    return node.isEnd 
}


/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
    node := this
    for _, char := range prefix {
        char = char - 'a'
        if node.next[char] == nil {
            return false
        }
        node = node.next[char]
    }
    return true 
}


/**
 * Your Trie object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(word);
 * param_2 := obj.Search(word);
 * param_3 := obj.StartsWith(prefix);
 */