Implement Trie (Prefix Tree) medium

Problem Statement

Implement a Trie (Prefix Tree) data structure.

A trie is a tree-like data structure used for efficient retrieval of keys in a dataset of strings. There are operations to insert and search keys (words) in the trie. For a given prefix, it also has the ability to check if there is any word with that prefix.

Example 1

Input
["Trie", "insert", "search", "search", "startsWith"]
[[], ["apple"], ["apple"], ["app"], ["app"]]
Output
[null, null, true, false, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true

Example 2

Input
["Trie", "insert", "insert", "search", "search", "startsWith", "startsWith"]
[[], ["app"], ["appl"], ["app"], ["appl"], ["app"], ["appl"]]
Output
[null, null, null, true, true, true, true]

Explanation
Trie trie = new Trie();
trie.insert("app");
trie.insert("appl");
trie.search("app");     // returns true
trie.search("appl");    // returns true
trie.startsWith("app"); // returns true
trie.startsWith("appl");// returns true

Steps

1. Trie Node Structure: Define a TrieNode class to represent each node in the Trie. Each node will store a boolean indicating whether it represents the end of a word and an array (or map) of children nodes, indexed by the character.

2. Trie Class: Create a Trie class with the following methods:

   • insert(word: string): Inserts a word into the Trie.
   • search(word: string): Checks if a word exists in the Trie.
   • startsWith(prefix: string): Checks if there's any word with the given prefix.

3. Insertion: Traverse the Trie using the characters of the word. If a character is not found, create a new node. Mark the last node as the end of a word.

4. Search: Traverse the Trie using the characters of the word. If a character is not found, the word doesn't exist. If the traversal completes and the last node is marked as the end of a word, the word exists.

5. startsWith: Similar to search, but it doesn't require the last node to be marked as the end of a word.

Explanation

The Trie efficiently stores words by sharing prefixes. Instead of storing entire words individually, it stores common prefixes only once. This leads to significant space savings, especially when many words share prefixes. The time complexity for insert, search, and startsWith is O(m), where m is the length of the word or prefix, because we traverse at most m nodes.

Code

class TrieNode {
    children: { [char: string]: TrieNode } = {};
    isEndOfWord: boolean = false;
}

class Trie {
    root: TrieNode;

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

    insert(word: string): void {
        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(word: string): boolean {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return node.isEndOfWord;
    }

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


/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */

Complexity

• Time complexity:

  • insert: O(m), where m is the length of the word.
  • search: O(m).
  • startsWith: O(m).

• Space complexity: O(N * m), where N is the number of words inserted and m is the maximum length of a word. In the worst-case scenario (no shared prefixes), each word occupies its own space in the Trie.