Coding Interview Questions | Implement Trie

January 17th, 2024

Implement Trie Problem Introduction:

This summary will talk about my solution to the implement trie problem as seen on leetcode here. A synopsis of the problem summary will be shown below:

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings.

There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

How do you solve the Implement Trie Problem?

Solution:

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

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

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;
  }
}

Implement Trie Solution Summary:

Below is a breakdown of the key aspects of the solution above for the implement trie problem:

TrieNode Class:

1. Children Map: Each node contains a Map called children to store the references to its child nodes. The keys of this map are characters, representing the letters of the inserted words.

2. End of Word Flag: The boolean isEndOfWord indicates whether the current node marks the end of a complete word.

Trie Class:

1. Insertion: The insert method efficiently adds words to the Trie, creating nodes as necessary.

2. Search: The search method checks for the existence of complete words in the Trie.

3. Prefix Matching: The startsWith method indicates whether any inserted word starts with a given prefix.

Complexities

1. Time Complexity: The time complexity for both insertion and search operations is O(m), where m is the length of the word.

2. Space Complexity: The space complexity of the solution is influenced by the number of unique characters and the length of the inserted words.