忘記您所知道的關於字符串搜索的一切 - 嘗試會讓您大吃一驚！

Trie資料結構簡介

trie，也稱為前綴樹，是一種高效的樹狀資料結構，用於儲存和檢索字串。它對於涉及字串搜尋、前綴匹配和自動完成功能的任務特別有用。

發音：

• 這是一個單音節字
• 最後的「ie」發音為長「e」音，類似「see」或「tree」
• 它與「pie」或「die」不押韻 這種發音有助於將其與其他外觀相似的單字區分開來，並強調其與資料檢索操作的聯繫。

何時使用 Trie

在您需要以下情況的情況下嘗試是理想的選擇：

1. 快速執行基於前綴的搜尋
2. 實現自動完成功能
3. 儲存單字字典以進行拼字檢查
4. 高效儲存和檢索具有公共前綴的字串 ## 可視化 Trie

讓我們想像一個包含單字「cat」、「car」和「dog」的特里樹：

       root
     /   |   \
    c    d    ...
   /     |
  a      o
 / \     |
t   r    g

每個節點代表一個字符，從根節點到葉節點的路徑組成完整的單字。

在 JavaScript 中實作 Trie

讓我們用 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

守則解釋

1. class TrieNode：表示 trie 中的一個節點。每個節點都有：： 一個用於儲存子節點的物件： 一個布林標誌，用於標記單字的結尾
2. class Trie：主要的 trie 結構及其方法：
   • 插入：在特里樹上加上一個單字
   • 搜尋：檢查單字是否存在於 trie
   • startsWith：檢查 trie 中是否有任何單字以給定前綴開頭
3. 該方法遍歷 trie，為不存在的字元建立新節點，並將最後一個節點標記為單字的結尾。
4. 該方法沿著給定單字的路徑遍歷 trie，如果找到整個單字並將其標記為完整單詞，則返回。
5. 該方法類似，但只檢查給定的前綴是否存在於 trie 中，而不管它是否是一個完整的單字。

時間與空間複雜度

• 時間複雜度：
  • 插入：O(m)，其中 m 是單字的長度
  • 搜尋：O(m)，其中 m 是單字的長度
  • StartsWith：O(m)，其中 m 是前綴的長度
• 空間複雜度：O(n * m)，其中n是單字數，m是單字的平均長度

Tries 為字串相關操作提供了出色的效能，特別是在處理大量具有公共前綴的單字時。它們提供快速查找和前綴匹配，這使得它們在自動完成系統、IP 路由表和字典實現等各種應用中具有無價的價值。

如果您喜歡本教程，請在此處關注我，並在 X/Twitter 上關注我：@turckalicious。本文是在 Wonderfall (https://wonderfall.xyz) 的幫助下完成的，這是一款由人工智慧驅動的互動式文件編輯器，可幫助您更快地研究、寫作和迭代。

以上是忘記您所知道的關於字符串搜索的一切 - 嘗試會讓您大吃一驚！的詳細內容。更多資訊請關注PHP中文網其他相關文章！