Trie树,也称前缀树,是一种用于高效存储和检索字符串的数据结构,广泛应用于自动补全、拼写检查和IP路由等场景。
插入新单词需要遍历Trie树,对于不存在的字符,创建新的节点。
查找单词通过遍历Trie树,检查单词是否存在。
检查Trie树中是否存在以特定前缀开头的单词。
class TrieNode {
constructor() {
this.children = {}; // 存储子节点
this.isWordEnd = false; // 标记单词结尾
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
// 插入单词
insert(word) {
let node = this.root;
for (let char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
node.isWordEnd = true; // 标记单词结尾
}
// 查找单词
search(word) {
let node = this.root;
for (let char of word) {
if (!node.children[char]) {
return false;
}
node = node.children[char];
}
return node.isWordEnd;
}
// 检查是否存在以指定前缀开头的单词
startsWith(prefix) {
let node = this.root;
for (let char of prefix) {
if (!node.children[char]) {
return false;
}
node = node.children[char];
}
return true;
}
}
// 示例用法
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple")); // true
console.log(trie.search("app")); // false
console.log(trie.startsWith("app")); // true
trie.insert("app");
console.log(trie.search("app")); // true
删除单词需要递归方法,删除不再需要的节点。
delete(word, node = this.root, depth = 0) {
if (depth === word.length) {
if (!node.isWordEnd) return false; // 单词不存在
node.isWordEnd = false;
return Object.keys(node.children).length === 0; // 检查节点是否有子节点
}
const char = word[depth];
if (!node.children[char]) return false;
const shouldDeleteChild = this.delete(word, node.children[char], depth + 1);
if (shouldDeleteChild) {
delete node.children[char];
return Object.keys(node.children).length === 0 && !node.isWordEnd;
}
return false;
}
计算有多少单词以给定前缀开头。
countWordsWithPrefix(prefix) {
let node = this.root;
for (let char of prefix) {
if (!node.children[char]) return 0;
node = node.children[char];
}
return this._countWords(node);
}
_countWords(node) {
let count = node.isWordEnd ? 1 : 0;
for (let char in node.children) {
count += this._countWords(node.children[char]);
}
return count;
}
给定前缀,返回所有以该前缀开头的单词。
getWordsWithPrefix(prefix) {
let node = this.root;
for (let char of prefix) {
if (!node.children[char]) return [];
node = node.children[char];
}
return this._collectWords(node, prefix);
}
_collectWords(node, prefix) {
let results = [];
if (node.isWordEnd) results.push(prefix);
for (let char in node.children) {
results = results.concat(this._collectWords(node.children[char], prefix + char));
}
return results;
}