Word Search II — Trie + DFS Backtracking on a Grid

Problem and Topic Statement#

Word Search II (LeetCode 212) — given an m by n grid of characters and a list of words, return all words from the list that can be formed by sequences of adjacent (up, down, left, right) cells, where the same cell may not be used more than once per word.

This problem is the gold standard for combining two techniques you would otherwise learn separately: trie construction over a dictionary, and DFS backtracking over a grid. Run them together and the resulting algorithm is dramatically faster than the naive search-each-word-independently approach.

Why This Topic Matters#

Word Search II is one of the most asked hard-tier interview questions at Meta, Google, Amazon, and Apple. It tests three skills in tandem — trie design, grid traversal, and backtracking with state restoration — and rewards strong pruning instincts. Few questions stress all of those at once.

In production, the trie-plus-backtrack pattern shows up in autocomplete-on-keyboard apps such as Swype gesture typing, boggle-style game solvers, OCR word verification, and entity linking against a dictionary. Whenever you have a fixed dictionary and a constrained traversal graph, this pattern is the right hammer.

The algorithmic skill the question develops is pruning by shared prefix. Without a trie, searching 5,000 words on a 10 by 10 board means 5,000 independent DFS scans. With a trie, you walk the board once and prune any path that does not match a known prefix — paying the dictionary cost as a one-time setup. That insight, amortising work across queries via a shared structure, is the heart of suffix arrays, Aho-Corasick, and inverted indexes.

The Core Insight#

The naive approach runs DFS for every word, costing O(W * M * N * 4^L) where W is the number of words and L is max word length. Most of that work is wasted because many words share prefixes; searching apple and apply repeats the appl exploration four times.

The trie approach inverts the loop. Build a trie of all dictionary words, marking each terminal node with the full word. Then for each starting cell, DFS the grid while simultaneously walking the trie. At each step, only proceed if the current cell's character is a child of the current trie node. When the trie node carries a stored word, record it as a match and clear the node to prevent duplicates.

Three pruning steps that matter:

1. Mark and unmark cells during DFS to enforce the no-reuse constraint. Use a sentinel like # so you do not allocate a visited matrix.
2. Clear the word at the trie node when matched. This avoids a hash set of seen words and the duplicate cost.
3. Trim leaf branches of the trie when their word has been consumed. This is the secret to outperforming the basic trie approach on large dictionaries — once a leaf has matched, removing it shrinks the search space for subsequent DFS calls.

The complexity drops to roughly O(M * N * 4 * 3^(L-1)) where the 3 reflects that, after the first move, you cannot return to the previous cell. Practical performance is much better thanks to trie pruning.

Visual Dry Run / Worked Example#

Board:

o a a n
e t a e
i h k r
i f l v

Words: ["oath","pea","eat","rain"].

Trie:

root
+- o - a - t - h*  (word "oath")
+- p - e - a*      (word "pea")
+- e - a - t*      (word "eat")
+- r - a - i - n*  (word "rain")

Starting from (0,0) o, the trie has child o, so DFS follows o. At (0,1) a continues since the trie has child a. At (1,1) t continues. At (2,1) h marks the terminal oath — record and clear.

Starting from (1,0) e, the trie has child e. DFS to (1,1) a if available. Continue search until eat is found at e -> a -> t.

pea never starts because no p exists on the board. rain never starts because the path r -> a -> i -> n is not connected on this grid.

Result: ["oath","eat"].

Solution (Optimal)#

Python — Trie + DFS#

def findWords(board, words):
    trie = {}
    for w in words:
        node = trie
        for ch in w:
            node = node.setdefault(ch, {})
        node['$'] = w
 
    rows, cols = len(board), len(board[0])
    res = []
 
    def dfs(r, c, parent):
        ch = board[r][c]
        node = parent.get(ch)
        if not node:
            return
        word = node.pop('$', None)
        if word is not None:
            res.append(word)
        board[r][c] = '#'
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
                dfs(nr, nc, node)
        board[r][c] = ch
        if not node:
            parent.pop(ch, None)
 
    for r in range(rows):
        for c in range(cols):
            dfs(r, c, trie)
    return res

JavaScript — Trie + DFS#

function findWords(board, words) {
  const trie = {};
  for (const w of words) {
    let node = trie;
    for (const ch of w) {
      if (!node[ch]) node[ch] = {};
      node = node[ch];
    }
    node.$ = w;
  }
  const rows = board.length, cols = board[0].length;
  const res = [];
 
  const dfs = (r, c, parent) => {
    const ch = board[r][c];
    const node = parent[ch];
    if (!node) return;
    if (node.$) { res.push(node.$); delete node.$; }
    board[r][c] = '#';
    for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] !== '#') {
        dfs(nr, nc, node);
      }
    }
    board[r][c] = ch;
    if (Object.keys(node).length === 0) delete parent[ch];
  };
 
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      dfs(r, c, trie);
  return res;
}

Complexity: O(W * L) trie build, O(M * N * 4 * 3^(L-1)) worst-case DFS. Space O(W * L) for the trie plus O(L) recursion.

Common Mistakes#

• Using a visited matrix instead of in-place marking. A visited matrix works but doubles memory; in-place sentinel marking is cleaner and standard.
• Storing matches in a set without clearing the trie node. Works but loses the optimisation; clearing the terminal marker plus pruning empty branches is the core speedup.
• Forgetting to backtrack. After DFS returns you must restore board[r][c] to its original character.
• Recomputing trie inside DFS. Build the trie once globally; pass nodes by reference into DFS.
• Not pruning empty branches. Without trie trimming a dictionary of 10,000 words on a small board still dominates runtime; trim leaves up the chain on the way back.

Interview Tips#

Start by stating why a trie is the right structure: shared prefixes mean shared work. Sketch the brute force first ("for each word, run Word Search I") and call out its O(W * M * N * 4^L) cost.

Walk through trie construction in code, then DFS. Emphasise three optimisations explicitly: in-place marking, clearing the terminal word marker, and pruning empty branches. Many candidates skip the third; FAANG interviewers reward you for naming it.

If asked about the worst case, point out that trie pruning is a heuristic — adversarial inputs (a very dense board where every word starts everywhere) still trigger the upper bound. The practical speed comes from the dictionary structure of natural English, not the worst case.

Follow-up Questions#

1. What if words can reuse cells? The constraint disappears; DFS without marking. The trie still helps amortise prefix work.
2. How would you parallelise this? Partition the board into starting cells across workers, sharing the trie read-only.
3. What if the dictionary is gigabytes large? Use a disk-backed trie or a DAWG (directed acyclic word graph) which deduplicates suffixes.
4. Can Aho-Corasick replace the trie here? Aho-Corasick is for linear text, not 2D grids. Tries are the right structure for grid backtracking.
5. How would you support fuzzy matching with one substitution allowed? Track an "errors used" counter per DFS frame.

Key Takeaways#

• Word Search II combines trie and grid backtracking; neither alone is sufficient and both together produce the optimal solution.
• The trie amortises shared prefix work across the dictionary, replacing a per-word O(M * N * 4^L) DFS with a single grid sweep.
• Three optimisations matter most: in-place sentinel marking, clearing matched word markers, and pruning empty trie branches.
• The pattern generalises to any "search a dictionary on a constrained graph" problem — boggle, gesture typing, autocomplete on a keyboard, OCR word lookup.
• Always sketch the brute force first, name the trie optimisation, and call out the three pruning tricks explicitly. FAANG interviewers grade for the third one.
• Worst-case complexity stays exponential in word length; the practical win comes from dictionary structure, not theoretical guarantees.