题目链接：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);
*/
