前缀树的结构:

ZOsfOp

结点的话本身不存储任何单词,它只存它要去到下一个路径上面这个路径代表的字符。

基本性质

  1. 结点本身不存储完整的单词。
  2. 从根节点到某一结点,路径上经过的字符连接起来,为该节点对应的字符串。
  3. 每个节点的所有子节点路径代表的字符都不相同。

走过的边就形成了单词

前缀树中的单词可以存储额外的信息,例如频次,后续的话我们就可以给用户做相应的推荐,

Oltd0z

因为每个节点后面都有26个可能的字母出现,因此最多有26个分支

空间相对消耗比较大,但是查询的次数就是单词的长度

核心思想:

空间换时间,同时可以利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

前缀树的实现:

假设只有26个英文字母忽略其他的字符。

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
type Trie struct {
endOfWord bool
children [26]*Trie
}


/** Initialize your data structure here. */
func Constructor() Trie {
return Trie{} //这里系统会帮助我们提前创建好endOfWord以及children
}


/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
cur := this
for _, val := range word {
if cur.children[val-'a'] != nil {
cur = cur.children[val-'a']
} else {
cur.children[val-'a'] = &Trie{}
cur = cur.children[val-'a']
}
}

cur.endOfWord = true
}


/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
cur := this
for _, val := range word {
if cur.children[val-'a'] != nil {
cur = cur.children[val-'a']
} else {
return false
}
}
return cur.endOfWord
}


/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
cur := this
for _, val := range prefix {
if cur.children[val-'a'] != nil {
cur = cur.children[val-'a']
} else {
return false
}
}
return 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);
*/

评论