curTain

简介

前缀树是N叉树的一种特殊形式。前缀树的每一个节点通常表示一个字符或者字符串。每一个节点拥有多个不同的子节点。值得注意的是,根节点表示空字符串。

前缀树的一个重要的特性是,节点所有的后代都与该节点相关的字符串有着共同的前缀。这就是前缀树名称的由来。

API设计

根据标题图可知,可以将前缀树分为两个对象,节点对象和前缀树对象,他们的功能各不相同

节点对象 TrieNode

  1. val: string 用来存储当前节点的值
  2. children: object 用来存储子节点
  3. isWord: boolean 用来表示是一个单词
  4. add(val: string): TrieNode 插入节点,并返回插入的节点

前缀树对象 Trie

  1. root: TrieNode 存储节点
  2. insert(word: string): void 向树中插入词语
  3. search(word: string): boolean 查找是否有该词语
  4. startsWith(prefix: string): boolean 前缀词语

实现

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// 节点
var TrieNode = function ( val = "" ){
// 一个节点只保存一个值
this.val = val
// 用来存储子节点
this.children = {}
// 标记单词结束
this.isWord = false
}

// 向当前节点添加子节点
TrieNode.prototype.add = function( val ){
let child = new TrieNode( val )
this.children[val] = child
return this.children[val]
}

/**
* Initialize your data structure here.
*/
var Trie = function() {
this.root = new TrieNode("")
};

/**
* Inserts a word into the trie.
* @param {string} word
* @return {void}
*/
Trie.prototype.insert = function(word) {
let current = this.root
let words = word.split("")
for( let item of words ){
if( current.children[ item ] ){
current = current.children[item]
} else {
current = current.add( item )
}
}
current.isWord = true
};

/**
* Returns if the word is in the trie.
* @param {string} word
* @return {boolean}
*/
Trie.prototype.search = function(word) {
let current = this.root
let words = word.split("")
for( let item of words ){
if( current.children[item] ){
current = current.children[item]
} else {
return false
}
}
return current.isWord
};

/**
* Returns if there is any word in the trie that starts with the given prefix.
* @param {string} prefix
* @return {boolean}
*/
Trie.prototype.startsWith = function(prefix) {
let current = this.root
let prefixs = prefix.split("")
for( let item of prefixs ){
if( current.children[item] ){
current = current.children[item]
} else {
return false
}
}
return true
};

参考材料

数据结构与算法(十一)Trie字典树

数据结构的故事之二叉树, 前缀树, N叉树

leetcode-208. 实现 Trie (前缀树)


 评论