實(shí)現(xiàn)一個(gè) Trie (前綴樹(shù))，包含 insert, search, 和 startsWith 這三個(gè)操作。

示例:

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
說(shuō)明:

你可以假設(shè)所有的輸入都是由小寫(xiě)字母 a-z 構(gòu)成的。
保證所有輸入均為非空字符串。

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/implement-trie-prefix-tree
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

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
}