08 — Trie

What is a Trie?

Tree-like data structure for prefix-based string operations.

Words: ["apple", "app", "apt", "bat", "bar"]

         (root)
        /      \
       a        b
      /          \
     p            a
    / \          / \
   p   t*       t*  r*
   |
   l
   |
   e*

* = end of word

---

Implementation

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEnd = false;
}

class Trie {
  private root = new TrieNode();
  
  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) {
        node.children.set(ch, new TrieNode());
      }
      node = node.children.get(ch)!;
    }
    node.isEnd = true;
  }
  
  search(word: string): boolean {
    const node = this.findNode(word);
    return node !== null && node.isEnd;
  }
  
  startsWith(prefix: string): boolean {
    return this.findNode(prefix) !== null;
  }
  
  private findNode(s: string): TrieNode | null {
    let node = this.root;
    for (const ch of s) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch)!;
    }
    return node;
  }
}

L = length of word/prefix

---

Autocomplete

class Trie {
  // ... previous methods ...
  
  autocomplete(prefix: string, limit = 10): string[] {
    const node = this.findNode(prefix);
    if (!node) return [];
    
    const results: string[] = [];
    
    function dfs(node: TrieNode, path: string) {
      if (results.length >= limit) return;
      if (node.isEnd) results.push(path);
      
      for (const [ch, child] of node.children) {
        dfs(child, path + ch);
      }
    }
    
    dfs(node, prefix);
    return results;
  }
}

const trie = new Trie();
['apple', 'app', 'application', 'apt', 'apply'].forEach(w => trie.insert(w));
trie.autocomplete('app'); // ['app', 'apple', 'application', 'apply']

---

Word Search (with wildcards)

// Search supporting '.' as wildcard
searchWithWildcard(word: string): boolean {
  function dfs(node: TrieNode, i: number): boolean {
    if (i === word.length) return node.isEnd;
    
    if (word[i] === '.') {
      for (const child of node.children.values()) {
        if (dfs(child, i + 1)) return true;
      }
      return false;
    }
    
    if (!node.children.has(word[i])) return false;
    return dfs(node.children.get(word[i])!, i + 1);
  }
  
  return dfs(this.root, 0);
}

---

XOR Trie (Maximum XOR)

Find maximum XOR of a number with any number in set.

class XORTrie {
  private root: [any, any] = [null, null]; // [0-child, 1-child]
  
  insert(num: number) {
    let node = this.root;
    for (let i = 31; i >= 0; i--) {
      const bit = (num >> i) & 1;
      if (!node[bit]) node[bit] = [null, null];
      node = node[bit];
    }
  }
  
  maxXor(num: number): number {
    let node = this.root;
    let result = 0;
    for (let i = 31; i >= 0; i--) {
      const bit = (num >> i) & 1;
      const want = 1 - bit; // Want opposite bit for max XOR
      if (node[want]) {
        result |= (1 << i);
        node = node[want];
      } else {
        node = node[bit];
      }
    }
    return result;
  }
}

---

Word Break (Trie + DP)

function wordBreak(s: string, wordDict: string[]): boolean {
  const trie = new Trie();
  for (const word of wordDict) trie.insert(word);
  
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true;
  
  for (let i = 0; i < n; i++) {
    if (!dp[i]) continue;
    let node = trie.root;
    for (let j = i; j < n; j++) {
      if (!node.children.has(s[j])) break;
      node = node.children.get(s[j])!;
      if (node.isEnd) dp[j + 1] = true;
    }
  }
  return dp[n];
}

---

Key Takeaways

• Trie = prefix tree — O(L) insert, search, prefix matching
• Perfect for autocomplete, spell check, word search, IP routing
• XOR Trie stores numbers bit-by-bit for maximum XOR queries
• Trie + DP = powerful combination for word break and similar problems
• Space: O(alphabet_size × total_characters) — can be large for many words