题目链接：208

思路

字典树Trie可以理解为一个特殊的多叉树。

type Trie struct {
    Neighbors [26]*Trie // 26个小写字母
    IsEnd     bool
}

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

/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
    cur := this
    for i := range word {
        index := word[i] - 'a'
        nxt := cur.Neighbors[index]
        if nxt == nil {
            cur.Neighbors[index] = &Trie{}
            nxt = cur.Neighbors[index]
        }
        cur = nxt
    }
    cur.IsEnd = true
}

func (this *Trie) searchPrefix(prefix string) *Trie {
    cur := this
    for i := range prefix {
        index := prefix[i] - 'a'
        nxt := cur.Neighbors[index]
        if nxt == nil {
            return nil
        }
        cur = nxt
    }
    return cur
}

/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
    node := this.searchPrefix(word)
    return node != nil && node.IsEnd
}

/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
    return this.searchPrefix(prefix) != nil
}

/**
 * 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);
 */