implement-trie.ts

/**
 * 208. Implement Trie (Prefix Tree)  (Medium)
 * Link: https://leetcode.com/problems/implement-trie-prefix-tree/
 *
 * Implement a trie with insert(word), search(word) (exact match), and
 * startsWith(prefix).
 *
 * Example:
 *   insert("apple");
 *   search("apple")   -> true
 *   search("app")     -> false
 *   startsWith("app") -> true
 *   insert("app"); search("app") -> true
 *
 * Approach:
 *   A tree of nodes, one edge per character. Each node has a map of children and
 *   an `isWord` flag. insert walks/creates nodes for each letter; search walks
 *   and checks isWord at the end; startsWith walks and only needs the path to
 *   exist. Every operation is proportional to the key length.
 *
 * Time:  O(L) per operation, L = word/prefix length.
 * Space: O(total characters inserted).
 */
class TrieNode {
  readonly children = new Map<string, TrieNode>();
  isWord = false;
}

export class Trie {
  private readonly root = new TrieNode();

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

  search(word: string): boolean {
    const node = this.walk(word);
    return node !== null && node.isWord;
  }

  startsWith(prefix: string): boolean {
    return this.walk(prefix) !== null;
  }

  /** Follow the path for `key`; return the terminal node or null if it breaks. */
  private walk(key: string): TrieNode | null {
    let node = this.root;
    for (const ch of key) {
      const next = node.children.get(ch);
      if (!next) return null;
      node = next;
    }
    return node;
  }
}