前缀树

type Trie struct {
	endOfWord bool
	children [26]*Trie
}


/** Initialize your data structure here. */
func Constructor() Trie {
	return Trie{}  //这里系统会帮助我们提前创建好endOfWord以及children
}


/** Inserts a word into the trie. */
func (this *Trie) Insert(word string)  {
	cur := this
	for _, val := range word {
		if cur.children[val-'a'] != nil {
			cur = cur.children[val-'a']
		} else {
			cur.children[val-'a'] = &Trie{}
			cur = cur.children[val-'a']
		}
	}

	cur.endOfWord = true
}


/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
	cur := this
	for _, val := range word {
		if cur.children[val-'a'] != nil {
			cur = cur.children[val-'a']
		} else {
			return false
		}
	}
	return cur.endOfWord
}


/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
	cur := this
	for _, val := range prefix {
		if cur.children[val-'a'] != nil {
			cur = cur.children[val-'a']
		} else {
			return false
		}
	}
	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);
 */