忘记您所知道的关于字符串搜索的一切

2024-09-21 12:01:15 编辑：抖狐科技来源：摘自互联网

忘记您所知道的关于字符串搜索的一切 - 尝试会让您大吃一惊！

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 中，而不管它是否是一个完整的单词。