前缀树

力扣练习题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
type TrieNode struct {  
    children [26]*TrieNode  
    isEnd    bool  //是否有以当前节点为结尾的单词
}  
type Trie struct {  
    root *TrieNode  
}  
  
func Constructor() Trie {  
    return Trie{root: &TrieNode{}}  
}  
func (t *Trie) Insert(word string) {  
    move := t.root  
    for _, ch := range word {  
       index := ch - 'a'  
       if move.children[index] == nil {  
          move.children[index] = &TrieNode{}  
       }  
       move = move.children[index]  
    }  
}  
func (t *Trie) search(word string) *TrieNode {  
    move := t.root  
    for _, ch := range word {  
       index := ch - 'a'  
       if move.children[index] == nil {  
          return nil  
       }  
       move = move.children[index]  
    }  
    return move  
}  
func (t *Trie) Search(word string) bool {  
    node := t.search(word)  
    //找到节点不一定就是找到单词，比如之前插入了apple，但是没有插入app，此时就应该返回false
    return node != nil && node.isEnd  
}  
func (t *Trie) StartsWith(prefix string) bool {  
    node := t.search(prefix)  
    return node != nil  
}

压缩前缀树