trie,也稱為前綴樹,是一種高效的樹狀資料結構,用於儲存和檢索字串。它對於涉及字串搜尋、前綴匹配和自動完成功能的任務特別有用。
在您需要以下情況的情況下嘗試是理想的選擇:
讓我們想像一個包含單字「cat」、「car」和「dog」的特里樹:
root / | \ c d ... / | a o / \ | t r g
每個節點代表一個字符,從根節點到葉節點的路徑組成完整的單字。
讓我們用 JavaScript 實作一個基本的 trie 結構:
class TrieNode { constructor() { this.children = {}; this.isEndOfWord = false; } } class Trie { constructor() { this.root = new TrieNode(); } // Insert a word into the trie 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; } // Search for a word in the trie 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(); // Insert words trie.insert("apple"); trie.insert("app"); trie.insert("banana"); console.log(trie.search("apple")); // Output: true console.log(trie.search("app")); // Output: true console.log(trie.search("appl")); // Output: false console.log(trie.startsWith("app")); // Output: true console.log(trie.startsWith("ban")); // Output: true console.log(trie.startsWith("cat")); // Output: false
Tries 為字串相關操作提供了出色的效能,特別是在處理大量具有公共前綴的單字時。它們提供快速查找和前綴匹配,這使得它們在自動完成系統、IP 路由表和字典實現等各種應用中具有無價的價值。
如果您喜歡本教程,請在此處關注我,並在 X/Twitter 上關注我:@turckalicious。本文是在 Wonderfall (https://wonderfall.xyz) 的幫助下完成的,這是一款由人工智慧驅動的互動式文件編輯器,可幫助您更快地研究、寫作和迭代。
以上是忘記您所知道的關於字符串搜索的一切 - 嘗試會讓您大吃一驚!的詳細內容。更多資訊請關注PHP中文網其他相關文章!