1
* 根节点: 不包含任何信息
2
* 每个节点: 树中的每个节点表示一个字符串中的一个字符, 从根节点到红色节点的一条路径表示一个字符串.

1
package trie
2

3
type Trie struct {
4
  isWorld bool
5
  child map[byte]*Trie
6
}
7

8

9
/** Initialize your data structure here. */
10
func Constructor() Trie {
11
  return Trie{child: make(map[byte]*Trie)}
12
}
13

14

15
/** Inserts a word into the trie. */
16
func (this *Trie) Insert(word string)  {
17
  node := this
18
  child := this.child
19
  for _, char := range word {
20
    if c, exists := child[byte(char)]; exists {
21
      node = c
22
      child = c.child
23
    } else {
24
      node = &Trie{
25
        isWorld: false,
26
        child:   make(map[byte]*Trie),
27
      }
28
      child[byte(char)] = node
29
      child = node.child
30
    }
31
  }
32
  node.isWorld = true
33
}
34

35

36
/** Returns if the word is in the trie. */
37
func (this *Trie) Search(word string) bool {
38
  isWorld := false
39
  child := this.child
40
  for _, char := range word {
41
    if c, exists := child[byte(char)]; !exists {
42
      isWorld = false
43
      break
44
    } else {
45
      isWorld = c.isWorld
46
      child = c.child
47
    }
48
  }
49
  return isWorld
50
}
51

52

53
/** Returns if there is any word in the trie that starts with the given prefix. */
54
func (this *Trie) StartsWith(prefix string) bool {
55
  child := this.child
56
  for _, char := range prefix {
57
    if c, exists := child[byte(char)]; !exists {
58
      return false
59
    } else {
60
      child = c.child
61
    }
62
  }
63
  return true
64
}