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

Introduction to Trie Data Structure

A trie, also known as a prefix tree, is an efficient tree-like data structure used for storing and retrieving strings. It's particularly useful for tasks involving string searches, prefix matching, and autocomplete functionality.

Pronunciation:

• It is a single syllable word
• The "ie" at the end is pronounced as a long "e" sound, similar to "see" or "tree"
• It does not rhyme with "pie" or "die" This pronunciation helps distinguish it from other similar-looking words and emphasizes its connection to data retrieval operations.

When to Use a Trie

Tries are ideal in scenarios where you need to:

1. Perform prefix-based searches quickly
2. Implement autocomplete features
3. Store a dictionary of words for spell-checking
4. Efficiently store and retrieve strings with common prefixes ## Visualizing a Trie

Let's visualize a trie containing the words "cat", "car", and "dog":

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

Each node represents a character, and the paths from root to leaf nodes form complete words.

Implementing a Trie in JavaScript

Let's implement a basic trie structure in JavaScript:

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

Explanation of the Code

1. class TrieNode: Represents a node in the trie. Each node has:: An object to store child nodes: A boolean flag to mark the end of a word
2. class Trie: The main trie structure with methods:
   • insert: Adds a word to the trie
   • search: Checks if a word exists in the trie
   • startsWith: Checks if any word in the trie starts with the given prefix
3. The method traverses the trie, creating new nodes for characters that don't exist and marking the last node as the end of a word.
4. The method traverses the trie along the path of the given word, returning if the entire word is found and marked as a complete word.
5. The method is similar to but only checks if the given prefix exists in the trie, regardless of whether it's a complete word.

Time and Space Complexity

• Time Complexity:
  • Insert: O(m), where m is the length of the word
  • Search: O(m), where m is the length of the word
  • StartsWith: O(m), where m is the length of the prefix
• Space Complexity:O(n * m), where n is the number of words and m is the average length of words

Tries offer excellent performance for string-related operations, especially when dealing with a large set of words with common prefixes. They provide fast lookups and prefix matching, making them invaluable in various applications such as autocomplete systems, IP routing tables, and dictionary implementations.

If you liked this tutorial follow me here and on X/Twitter at @turckalicious. This article was made with the help of Wonderfall (https://wonderfall.xyz), an AI-powered interactive document editor that helps you research, write, and iterate faster.

The above is the detailed content of Forget Everything You Know About String Searching - Tries Will Blow Your Mind!. For more information, please follow other related articles on the PHP Chinese website!