忘記您所知道的關於字符串搜索的一切 - 嘗試會讓您大吃一驚！-js教程-PHP中文網

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

Linda Hamilton

發布： 2024-09-21 06:24:32

原創

1028 人瀏覽過

Forget Everything You Know About String Searching - Tries Will Blow Your Mind!

Trie資料結構簡介

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

發音：

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

何時使用 Trie

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

快速執行基於前綴的搜尋
實現自動完成功能
儲存單字字典以進行拼字檢查
高效儲存和檢索具有公共前綴的字串 ## 可視化 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

登入後複製

守則解釋

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