实现 Trie（前缀树）

代码 · 当前高亮行随帧切换

1type Trie struct {
2    children [26]*Trie
3    isEnd    bool
4}
5 
6func Constructor() Trie {
7    return Trie{}
8}
9 
10func (this *Trie) Insert(word string) {
11    node := this
12    for _, c := range word {
13        idx := int(c - 'a')
14        if node.children[idx] == nil {
15            node.children[idx] = &Trie{}
16        }
17        node = node.children[idx]
18    }
19    node.isEnd = true
20}
21 
22func (this *Trie) Search(word string) bool {
23    node := this.searchPrefix(word)
24    return node != nil && node.isEnd
25}
26 
27func (this *Trie) StartsWith(prefix string) bool {
28    node := this.searchPrefix(prefix)
29    return node != nil
30}
31 
32func (this *Trie) searchPrefix(s string) *Trie {
33    node := this
34    for _, c := range s {
35        idx := int(c - 'a')
36        if node.children[idx] == nil {
37            return nil
38        }
39        node = node.children[idx]
40    }
41    return node
42}