a trie は、特にオートコンプリート、スペルチェック、IPルーティングなどのアプリケーションで、文字列を効率的に保存および検索するために使用されるツリーのようなデータ構造です。
単語を挿入するには、存在しない文字のトライを横断し、新しいノードを作成することが含まれます。
検索は、ノードを横断することにより、トライに単語が存在するかどうかをチェックします。
これは、Trieの単語が特定のプレフィックスで始まるかどうかをチェックします。
class TrieNode { constructor() { this.children = {}; // Stores child nodes this.isEndOfWord = false; // Marks the end of a word } } class Trie { constructor() { this.root = new TrieNode(); } // Insert a word 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.isEndOfWord = true; // Mark the end of the word } // Search for a word search(word) { let node = this.root; for (let char of word) { if (!node.children[char]) { return false; } node = node.children[char]; } return node.isEndOfWord; } // Check if any word starts with the given prefix startsWith(prefix) { let node = this.root; for (let char of prefix) { if (!node.children[char]) { return false; } node = node.children[char]; } return true; } } // Example usage 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.isEndOfWord) return false; // Word doesn't exist node.isEndOfWord = false; return Object.keys(node.children).length === 0; // Check if node has children } 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.isEndOfWord; } return false; }
countwordswithprefix(prefix){
let node = this.root;
for(let char of prefix){
if(!node.children [char])return 0;
node = node.children [char];
}
this._countwords(node);
}
_countwords(node){
count = node.isendofwordとしますか? 1:0;
for
count = this._countwords(node.children [char]);
}
返品数;
}
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.isEndOfWord ? 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.isEndOfWord) results.push(prefix); for (let char in node.children) { results = results.concat(this._collectWords(node.children[char], prefix char)); } return results; }
免責事項: 提供されるすべてのリソースの一部はインターネットからのものです。お客様の著作権またはその他の権利および利益の侵害がある場合は、詳細な理由を説明し、著作権または権利および利益の証拠を提出して、電子メール [email protected] に送信してください。 できるだけ早く対応させていただきます。
Copyright© 2022 湘ICP备2022001581号-3