Solving Implement Trie (Prefix Tree): Building a Searchable Data Structure

The "Implement Trie (Prefix Tree)" problem involves building a Trie, a special type of tree used to efficiently store a dynamic set of strings. Tries are used for searching, inserting, and performing prefix operations in a collection of strings.

Problem Statement

Design a Trie data structure that supports insertion, search, and prefix search operations efficiently.

Example of Trie Functionality

• Insert: Adding words like "apple" and "app" into the Trie.
• Search: Checking if a word like "apple" is in the Trie.
• Starts With: Checking if there are any words that start with a prefix like "app".

Solution Approach - Trie Implementation

export class TrieNode {
  children: Map<string, TrieNode>;
  isEndOfWord: boolean;

  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
  }
}

export class Trie {
  root: TrieNode;

  constructor() {
    this.root = new TrieNode();
  }

  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.isEndOfWord = true;
  }

  search(word: string): boolean {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        return false;
      }
      node = node.children.get(char)!;
    }
    return node.isEndOfWord;
  }

  startsWith(prefix: string): boolean {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) {
        return false;
      }
      node = node.children.get(char)!;
    }
    return true;
  }
}

Breaking Down the Solution

• TrieNode Class: Represents each node in the Trie, holding children and a flag to indicate end of a word.
• Trie Class: Implements the Trie with methods for insert, search, and startsWith.
• Efficient Operations: Leveraging the Trie structure for quick lookups and prefix searches.

Conclusion

Implementing a Trie is a crucial exercise in understanding tree-like data structures and their application in efficiently managing and searching strings.