切换主题
前缀树
实现前缀树（亦称作字典树），以仅包含26位小写字母或26位大写字母的字符串为例创建前缀树！
定义节点
首先定义前缀树的节点结构：
pass在前缀树中表示以该出字符结尾的前缀串的出现次数；end在前缀树中表示以该处字符结尾的字符串的出现次数；children在前缀树中表示*以该处字符为父节点的子字符串。
JavaScript
class TrieNode {
constructor() {
this.pass = 0
this.end = 0
this.children = Array(26)
}
}添加字符串
JavaScript
class Trie {
// 初始化根节点
constructor() {
this.root = new TrieNode()
}
insert(str) {
if (str == null) return
let node = this.root
node.pass++
for (const char of str) {
const idx = char.charCodeAt() - 'a'.charCodeAt()
if (node.children[idx] == null) { // 为空
node.children[idx] = new TrieNode()
}
node = node.children[idx]
node.pass++
}
node.end++
}
}搜索字符串
JavaScript
class Trie {
// 其它逻辑代码...
search(str) {
if (str == null) return 0
let node = this.root
for (const char of str) {
const idx = char.charCodeAt() - 'a'.charCodeAt()
// 在前缀数中没路前进了，但是查找字符串还没找到
if (node.children[idx] == null) {
return 0
}
node = node.children[idx]
}
return node.end
}
}搜索前缀串
JavaScript
class Trie {
// 其它逻辑代码...
prefix(str) {
if (str == null) return 0
let node = this.root
for (const char of str) {
const idx = char.charCodeAt() - 'a'.charCodeAt()
// 在前缀数中没路前进了，但是查找字符串还没找到
if (node.children[idx] == null) {
return 0
}
node = node.children[idx]
}
return node.pass
}
}删除字符串
JavaScript
class Trie {
// ...
delete(str) {
if (this.search(str) !== 0) { // 存在才能删除
node = this.root
node.pass--
for (const char of str) {
const idx = char.charCodeAt() - 'a'.charCodeAt()
// 当节点pass为0，说明其后续内容均已无效，应该删除
if (--node.children[idx].pass === 0) {
node.children[idx] = null
return
}
node = node.children[idx]
}
node.end--
}
}
}完整代码
完整代码对大量的重复逻辑进行了优化！
查看
JavaScript
class TrieNode {
constructor() {
this.pass = 0
this.end = 0
this.children = Array(26)
}
}
class Trie {
constructor() {
this.root = new TrieNode()
}
// 抽离公用逻辑
iterStr(str, node, type) {
for (const char of str) {
const idx = char.charCodeAt() - 'a'.charCodeAt()
if (type === 'search' || type === 'prefix') {
// 在前缀数中没路前进了，但是查找字符串还没找到
if (!node.children[idx]) return 0
} else if (type === 'insert') {
if (!node.children[idx]) {
node.children[idx] = new TrieNode()
}
} else if (type === 'delete') {
if (--node.children[idx].pass === 0) {
node.children[idx] = null
return
}
}
node = node.children[idx]
if (type === 'insert') node.pass++
}
return node
}
insert(str) {
if (str == null) return
let node = this.root
node.pass++
node = this.iterStr(str, node, 'insert')
node.end++
}
// 搜索 --> 出现次数
search(str) {
if (str == null) return 0
let node = this.root
node = this.iterStr(str, node, 'search')
return node.end
}
// 前缀数量
prefix(str) {
if (str == null) return 0
let node = this.root
node = this.iterStr(str, node, 'prefix')
return node.pass
}
// 删除
delete(str) {
if (this.search(str) !== 0) { // 存在才能删除
node = this.root
node.pass--
node = this.iterStr(str, node, 'delete')
if (!node) return
node.end--
}
}
}