208.实现 Trie (前缀树)

字典树

树的节点存储两个数据：

1. Count作为结束节点的次数（用来标识单词结束以及统计单词出现次数）
2. Edges存储从该节点还可以延伸下去的边（指针指向下一个节点），可以是数组也可以是map，map适用性更强。

   type Trie struct {
       Count int
       Edges map[byte]*Trie
   }
   
   func Constructor() Trie {
       return Trie{
           Count: 0,
           Edges: make(map[byte]*Trie),
       }
   }
   
   
   func (this *Trie) Insert(word string)  {
       curr := this
       for i := 0; i < len(word); i++ {
           next, ok := curr.Edges[word[i]]
           if !ok {
               next = &Trie{
                   Count: 0,
                   Edges: make(map[byte]*Trie),
               }
               curr.Edges[word[i]] = next
           }
   
           if i == len(word) - 1 {
               next.Count++
           }
           // fmt.Printf("curr: %v\n", curr)
   
           curr = next
   
       }
   }
   
   func (this *Trie) Search(word string) bool {
       curr := this
       ok := true
       for i := 0; i < len(word); i++ {
           if ok {
               curr, ok = curr.Edges[word[i]]  
           } else {
               return false
           }
       }
       return ok && curr.Count > 0
   }
   
   
   func (this *Trie) StartsWith(prefix string) bool {
       curr := this
       ok := true
       for i := 0; i < len(prefix); i++ {
           if ok {
               curr, ok = curr.Edges[prefix[i]]  
           } else {
               return false
           }
       }
       return ok && 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);
    */