Lab 07 — Trie Applications (Implement Trie + Word Search II)

Goal

Build a trie supporting insert, search, startsWith (LC 208), then use a trie to solve LC 212 — Word Search II — by pruning a DFS over a 2D grid against a trie of dictionary words. After this lab, the trie should be a reflex for any “many strings, prefix-shared, batch-query” problem.

Background Concepts

A trie (prefix tree) is a tree where each edge is labeled with one character and each path from the root spells a string. A node may carry an is_end flag meaning “a word terminates here”. Two strings sharing a prefix share the prefix path in the trie, giving O(L) per insert / search regardless of how many words exist — a fundamental advantage over hashtable + per-word check when prefixes overlap.

Children can be stored as:

  • Array of 26 (or 256) — fastest dispatch, fixed alphabet, slightly memory-heavy. Best for grid-DFS hot loops.
  • Hash map char → node — flexible alphabet, slower constant. Good for arbitrary Unicode or large alphabets.
  • Compressed (radix tree / Patricia) — collapse single-child chains; smaller memory, harder to implement.

For LC 212, the killer move is: instead of running KMP / search per word against the grid (O(W · cells)), build a trie of all words and run one DFS that explores the grid while walking the trie in parallel, terminating any branch whose current grid letter has no trie-child. This converts the cost from “many independent searches” into “one search with multi-end”.

Interview Context

Tries are asked at every FAANG with high frequency: Meta, Google, Amazon all have multiple variants in their pool. The pattern is “many strings share prefixes; query, autocomplete, or grid-search”. Recognizing the trie-prune-DFS reduction for LC 212 is a strong-hire signal — it’s a 5-line code change with a 100x speedup.

Cousins: autocomplete (LC 642), longest word in dictionary (LC 720), word break (LC 139 — sometimes trie-friendly), maximum xor of two numbers (LC 421 — bit-trie).

Problem Statement A (LC 208)

Implement Trie with insert(word), search(word) (exact match), startsWith(prefix) (any word with this prefix).

Problem Statement B (LC 212)

Given an m × n grid of letters and a list words, return all words that can be formed by a sequence of adjacent (4-directionally connected) cells in the grid, where each cell is used at most once per word.

Constraints

  • LC 208: ≤ 3 × 10⁴ ops; lowercase ASCII; word length ≤ 2000.
  • LC 212: 1 ≤ m, n ≤ 12; 1 ≤ |words| ≤ 3 × 10⁴; each word length ≤ 10; lowercase ASCII.

Clarifying Questions

  1. Are duplicate words possible in the dictionary? (LC 212: assume no, dedupe defensively.)
  2. Can the same cell be reused across different words? (Yes — only “once per word”.)
  3. Is alphabet exactly lowercase ASCII? (Yes — use array of 26.)

Examples

LC 212:

board = [['o','a','a','n'],
         ['e','t','a','e'],
         ['i','h','k','r'],
         ['i','f','l','v']]
words = ["oath", "pea", "eat", "rain"]
→ ["oath", "eat"]

Initial Brute Force

For each word, run a DFS from every starting cell that matches the word’s first letter; backtrack on dead ends.

Per-word DFS: O(m · n · 4^L). Total: O(W · m · n · 4^L). With W=3×10⁴, m·n=144, L=10: ~10¹⁰ ops. TLE.

Brute Force Complexity

O(W · m · n · 4^L). At the limits: 1.6 × 10¹⁰. TLE by 4 orders of magnitude.

Optimization Path

Trie-pruned DFS. Build a trie of all words once: O(total chars) ≈ 3 × 10⁵. Then run a single DFS from each cell, walking the trie in parallel; whenever a trie-child for the current letter is missing, prune. Whenever an is_end is hit, record that word.

Total: O(m · n · 4^L) for the DFS structure, but the effective branching is small because most paths are pruned within 2-3 chars. Practical speedup: ~100×.

Optimization on top: when a word is recorded, mark its trie-end node and prune empty trie branches as you backtrack — keeps the trie shrinking.

Final Expected Approach

  1. Build trie: each node has children[26], word: Optional[str] (set on insert at the terminal).
  2. For each cell (i, j), DFS:
    • Read c = board[i][j].
    • If node.children[c - 'a'] is None, return.
    • Descend: node = node.children[...].
    • If node.word: append to results, set node.word = None to dedupe.
    • Mark board[i][j] = '#' to prevent reuse.
    • Recurse 4 directions.
    • Restore board[i][j] = c.
  3. Return results.

Data Structures Used

  • TrieNode { children: List[Optional[TrieNode]], word: Optional[str] }.
  • 2D grid (mutable for the visited-mark trick).
  • Result list.

Correctness Argument

The trie-DFS enumerates exactly the set of (path-in-grid, path-in-trie) pairs where each step matches the current grid letter to a trie child. A word is reported iff the DFS reaches a trie node with word != None along a non-self-intersecting grid path — by construction this is exactly the set of words present in the grid. Setting node.word = None after recording deduplicates without affecting other paths (the children remain reachable for other words sharing this prefix).

board[i][j] = '#' ensures non-reuse: the only way to visit a cell already on the path is if the trie has ‘#’ as a child of the current node, which it doesn’t (alphabet is lowercase).

Complexity

OperationTimeSpace
Trie buildO(total characters in words)O(total characters)
DFS (worst)O(m · n · 4 · 3^(L-1)) per starting cellO(L) recursion
TotalO(m · n · 4 · 3^(L-1))O(W · L) trie + O(L) recursion

The 3^(L-1) (not 4^L) is because after the first step, you can’t immediately go back, so each node has ≤ 3 forward neighbors.

Implementation Requirements

class TrieNode:
    __slots__ = ('children', 'word')
    def __init__(self):
        self.children = [None] * 26
        self.word = None

def findWords(board, words):
    root = TrieNode()
    for w in words:
        node = root
        for c in w:
            i = ord(c) - ord('a')
            if node.children[i] is None:
                node.children[i] = TrieNode()
            node = node.children[i]
        node.word = w

    m, n = len(board), len(board[0])
    res = []

    def dfs(i, j, parent):
        c = board[i][j]
        if c == '#': return
        idx = ord(c) - ord('a')
        node = parent.children[idx]
        if node is None: return
        if node.word is not None:
            res.append(node.word)
            node.word = None
        board[i][j] = '#'
        for di, dj in ((-1,0),(1,0),(0,-1),(0,1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < m and 0 <= nj < n:
                dfs(ni, nj, node)
        board[i][j] = c
        # Optional pruning: if node has no children and no word, parent.children[idx] = None.

    for i in range(m):
        for j in range(n):
            dfs(i, j, root)
    return res

Tests

  • LC 212 sample → ["oath", "eat"].
  • Empty grid / empty word list → [].
  • Word equals a single cell: board=[['a']], words=["a"] → ["a"].
  • Word longer than grid: returns nothing.
  • Duplicate paths to same word: appears once thanks to node.word = None.
  • Words sharing prefixes: words=["oath", "oat"] — both should be found if both are present.
  • Stress: random grids of size 12×12, random word list of 100 words length 5; verify against per-word DFS brute force.

Follow-up Questions

  1. “How would you support deletion?” → reference-count children or do recursive cleanup; tricky due to shared prefixes.
  2. “Autocomplete with frequency.” → store count per word at the terminal; on prefix lookup, walk the subtree and pick top-k by count (or maintain a per-node max-heap).
  3. “What if the alphabet is Unicode?” → switch from children[26] to a dict. Per-node memory grows but dispatch is O(1) hash.
  4. “Compress the trie.” → radix / Patricia trie collapses single-child chains; helpful when you have million-word dictionaries (e.g., DNS).
  5. “Bit trie for max-XOR (LC 421).” → trie of binary representations, depth 30 for 32-bit ints; greedy descent picks the opposite bit when possible.

Product Extension

Search-as-you-type / autocomplete: as a user types each character, walk the trie down one node and emit the top-k completions stored at that node. Production search engines (ES, Solr) build inverted indices, but for “small dictionary, fast prefix lookup” use cases (CLI command completion, query suggestion within an admin tool), an in-memory trie is the right call. DNS resolution uses radix tries internally.

Language/Runtime Follow-ups

  • Python: __slots__ on TrieNode trims memory by ~40%. For LC 212 use list of children rather than dict — dict’s per-key overhead dominates at this size.
  • Java: TrieNode { TrieNode[] children = new TrieNode[26]; String word; }. JIT inlines the array dispatch.
  • Go: type TrieNode struct { children [26]*TrieNode; word string }. Value-typed array of pointers is cache-friendlier than a slice.
  • C++: struct TrieNode { array<TrieNode*, 26> children{}; string word; };. Use a deque<TrieNode> arena to avoid new per node.
  • JS/TS: plain object {children: Array(26), word: null} works; for large tries Map with char keys uses less memory than 26-array per node.

Common Bugs

  1. Forgetting to mark board[i][j] = '#' before recursing — same cell reused, wrong matches reported.
  2. Forgetting to restore board[i][j] = c after recursion — corrupts the board for subsequent DFS calls.
  3. Recording the word multiple times because the same prefix is reached via different paths. Fix: node.word = None after recording.
  4. Storing the word only at the terminal — works if you carry the path string in DFS, wasteful otherwise. Correct: store the word at the terminal trie node.
  5. Initializing children = [None] (length 1) instead of [None] * 26 — silent error at first non-‘a’ insert.
  6. Walking the trie before reading the grid letter — off-by-one; you should read the grid letter, look up parent.children[c], then descend.

Debugging Strategy

Trace the DFS on the LC 212 sample by hand: starting at (0, 0)=‘o’, root has child ‘o’ → ok; recurse to (1, 0)=‘e’ or (0, 1)=‘a’; descend to “oa” → child ‘a’; etc. If your output is missing words, add print(node.word) on the entry to dfs and verify the word terminations are correctly placed in the trie. If your output has spurious words, the visited-mark or the is_end placement is wrong.

Mastery Criteria

  • Wrote Trie class with insert/search/startsWith in <8 minutes.
  • Solved LC 212 in <30 minutes from cold start.
  • Stated the speedup over per-word DFS and the complexity of the combined DFS.
  • Used node.word storage (not is_end + carry-string) for clean dedup.
  • Picked array-of-26 over hashmap for performance and justified it.
  • Solved LC 421 (bit-trie max XOR) using the same structure.