实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true
说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

package leetcode

type Trie struct {
    Root *TrieNode
}

type TrieNode struct {
    Children map[rune]*TrieNode
    End      bool
}

func NewTrie() *Trie {
    t := &Trie{}
    t.Root = NewTrieNode()
    return t
}

func NewTrieNode() *TrieNode {
    n := &TrieNode{}
    n.Children = make(map[rune]*TrieNode)
    n.End = false
    return n
}

/** Initialize your data structure here. */
func Constructor() Trie {
    t := Trie{}
    t.Root = NewTrieNode()
    return t
}

/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
    if len(word) < 1 {
        return
    }
    chars := []rune(word)
    slen := len(chars)
    node := this.Root
    for i := 0; i < slen; i++ {
        if _, exist := node.Children[chars[i]]; !exist {
            node.Children[chars[i]] = NewTrieNode()
        }
        node = node.Children[chars[i]]
    }
    node.End = true
}

/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
    chars := []rune(word)
    slen := len(chars)
    node := this.Root
    for i := 0; i < slen; i++ {
        if _, exists := node.Children[chars[i]]; !exists {
            return false
        }
        node = node.Children[chars[i]]
        if node.End == true && i == slen-1 {
            return true
        }
    }
    return false
}

/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
    chars := []rune(prefix)
    slen := len(chars)
    node := this.Root
    for i := 0; i < slen; i++ {
        if _, exists := node.Children[chars[i]]; !exists {
            return false
        }
        node = node.Children[chars[i]]
    }
    return true
}