认识
Trie(发音类似 "try")或者说前缀树, 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查、处理字符串匹配问题的数据结构、解决集合中查找固定前缀字符串等场景。
实现
字典树结构
Trie 又称前缀树或字典树,是一棵有根树,其每个节点包含以下字段:
-
children: 数组长度为
26
,即小写英文字母的数量.此时children[0]
对应小写字母a
,children[1]
对应小写字母b
,…,children[25]
对应小写字母z
-
布尔字段:
isEnd
,表示该节点是否为字符串的结尾
插入字符串
我们从字典树的根开始,插入字符串。对于当前字符对应的子节点,有两种情况:
-
子节点存在。沿着指针移动到子节点,继续处理下一个字符
-
子节点不存在。创建一个新的子节点,记录在
children
数组的对应位置上,然后沿着指针移动到子节点,继续搜索下一个字符
重复以上步骤,直到处理字符串的最后一个字符,然后将当前节点标记为字符串的结尾。
insert(word) {
let node = this;
for (let i = 0; i < word.length; i++) {
const char = word[i];
const index = char.charCodeAt() - "a".charCodeAt();
if (node.children[index] === 0) {
node.children[index] = new Trie();
}
node = node.children[index];
}
node.isEnd = true;
}