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

百变鹏仔 2个月前 (10-14) #JavaScript

文章标签让您

trie数据结构简介

trie，也称为前缀树，是一种高效的树状数据结构，用于存储和检索字符串。它对于涉及字符串搜索、前缀匹配和自动完成功能的任务特别有用。

发音：

何时使用 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 usageconst trie = new Trie();// Insert wordstrie.insert("apple");trie.insert("app");trie.insert("banana");console.log(trie.search("apple"));    // Output: trueconsole.log(trie.search("app"));      // Output: trueconsole.log(trie.search("appl"));     // Output: falseconsole.log(trie.startsWith("app"));  // Output: trueconsole.log(trie.startsWith("ban"));  // Output: trueconsole.log(trie.startsWith("cat"));  // Output: false

守则解释

class trienode：表示 trie 中的一个节点。每个节点都有：：一个用于存储子节点的对象：一个布尔标志，用于标记单词的结尾
class trie：主要的 trie 结构及其方法：
该方法遍历 trie，为不存在的字符创建新节点，并将最后一个节点标记为单词的结尾。
该方法沿着给定单词的路径遍历 trie，如果找到整个单词并将其标记为完整单词，则返回。
该方法类似，但只检查给定的前缀是否存在于 trie 中，而不管它是否是一个完整的单词。

时间和空间复杂度

空间复杂度：o(n * m)，其中n是单词数，m是单词的平均长度

tries 为字符串相关操作提供了出色的性能，特别是在处理大量具有公共前缀的单词时。它们提供快速查找和前缀匹配，这使得它们在自动完成系统、ip 路由表和字典实现等各种应用中具有无价的价值。

如果您喜欢本教程，请在此处关注我，并在 x/twitter 上关注我：@turckalicious。本文是在 wonderfall (https://wonderfall.xyz) 的帮助下完成的，这是一款人工智能驱动的交互式文档编辑器，可帮助您更快地研究、写作和迭代。

文章推荐

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

trie数据结构简介

发音：

何时使用 trie

在 javascript 中实现 trie

守则解释

时间和空间复杂度

JavaScript如何获取宏控件数据？

JavaScript怎样读取宏控件数据？

JavaScript获取宏控件数据的技巧

探究JavaScript与Java的联系和区别

javascript:void(o)如何解决？