Word Search II — Trie + Backtracking on a Grid

Problem Statement#

LeetCode 212 — Word Search II | Difficulty: Hard

Given an m x n board of characters and a list of strings words, return all words on the board. A word is constructed from letters of sequentially adjacent cells (horizontally or vertically neighbouring). The same letter cell may not be used more than once in a word.

Constraints:

• 1 <= m, n <= 12
• board[i][j] is a lowercase English letter.
• 1 <= words.length <= 3 * 10^4
• 1 <= words[i].length <= 10
• All words[i] consist of lowercase English letters and are unique.

Examples:

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

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

Why This Problem Matters#

Word Search II is the canonical "use a trie or you will TLE" problem. The naive approach — running LC 79 word-search backtracking once per word — costs O(W times m times n times 4^L). With 30,000 words and L up to 10, that is well over 10^15 operations.

The trie approach inverts the search. Instead of asking "for each word, can I find it?", we ask "for each starting cell, what words live in this neighbourhood?" One DFS traversal collects all answers simultaneously. This is a recurring FAANG pattern — Google, Amazon, Microsoft, and Uber all ask variants. The technique generalises to multi-pattern matching, log scanning, and search auto-suggest backends.

The Core Insight#

Three ideas combine:

1. Trie of words — Insert every dictionary word into a trie. Each leaf stores the full word string for easy collection.
2. Single grid DFS — Start a DFS from every cell. The DFS state is the current trie node. When the next grid letter is not a child of the current trie node, prune immediately.
3. Mark-and-restore backtracking — Temporarily overwrite the cell with a sentinel like "#" to prevent revisits, restore after the recursive call.

A crucial optimisation is leaf pruning: once a word is found, set the trie node's word = None so it is not collected twice, and lazily delete leaf nodes whose subtree is empty so future DFS calls skip them entirely. This single change typically cuts runtime by an order of magnitude.

Visual Dry Run#

Take a smaller example — board [["a","b"],["c","d"]] with words ["ab","ad","bc"].

Trie:
            root
          /  |  
         a   b
        / \   \
       b   d   c
       *   *   *

DFS starting at (0,0)='a':

node = root → child 'a' exists, descend
  current cell = (0,0), trie at 'a' node
  try (0,1)='b' → 'a' has child 'b', descend → b.word="ab" COLLECT
  try (1,0)='c' → 'a' has no child 'c', prune
  try (0,1) restore... already done, backtrack
  ... eventually try 'd' via path (0,0)→(1,0)? not adjacent in trie

Notice how the moment the grid letter is missing from the trie, we abandon — we never explore deeper paths that could not match any word.

Solution (Optimal) — Trie + Grid DFS with Pruning#

Python#

class TrieNode:
    __slots__ = ("children", "word")
    def __init__(self):
        self.children = {}
        self.word = None      # store full word at terminal node
 
class Solution:
    def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:
        # 1) Build the trie
        root = TrieNode()
        for w in words:
            node = root
            for ch in w:
                node = node.children.setdefault(ch, TrieNode())
            node.word = w   # tag terminal with full word
 
        m, n = len(board), len(board[0])
        out: list[str] = []
 
        def dfs(r: int, c: int, parent: TrieNode) -> None:
            ch = board[r][c]
            node = parent.children.get(ch)
            if node is None:
                return
            if node.word is not None:
                out.append(node.word)
                node.word = None  # avoid duplicates
 
            board[r][c] = "#"     # mark visited
            for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and board[nr][nc] != "#":
                    dfs(nr, nc, node)
            board[r][c] = ch       # restore
 
            # leaf pruning — remove dead branches
            if not node.children:
                parent.children.pop(ch, None)
 
        for i in range(m):
            for j in range(n):
                dfs(i, j, root)
 
        return out

JavaScript#

var findWords = function (board, words) {
  // Build trie
  const root = {};
  for (const w of words) {
    let node = root;
    for (const ch of w) {
      if (!node[ch]) node[ch] = {};
      node = node[ch];
    }
    node.word = w;
  }
 
  const m = board.length, n = board[0].length;
  const out = [];
 
  const dfs = (r, c, parent) => {
    const ch = board[r][c];
    const node = parent[ch];
    if (!node) return;
    if (node.word) {
      out.push(node.word);
      node.word = null;
    }
    board[r][c] = "#";
    const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] !== "#") {
        dfs(nr, nc, node);
      }
    }
    board[r][c] = ch;
    // Prune empty subtree
    if (Object.keys(node).length === 0) delete parent[ch];
  };
 
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      dfs(i, j, root);
    }
  }
  return out;
};

Complexity#

• Time: O(m times n times 4^L) worst case, where L is the max word length. With aggressive pruning, far below this in practice.
• Space: O(K) for the trie where K is total characters across all words, plus O(L) recursion depth.

Common Mistakes#

1. Running LC 79 once per word — TLE. The whole point is to amortise the grid traversal across all words.
2. Forgetting to null out the word after collecting — produces duplicate answers in the output.
3. Skipping leaf pruning — solutions still pass but are 5–10x slower; many interviewers treat this as the "good vs great" signal.
4. Using a visited set instead of in-place mutation — works but adds O(m times n) space per recursive frame; in-place is faster and idiomatic.
5. Restoring the cell before the recursive call returns — must restore after the four neighbour calls, not before.
6. Using a 26-array trie when most slots are empty — for 30k words you waste memory; a hash map or object is fine here.

Interview Tips#

• Start by stating the naive approach and its complexity, then pivot to the trie. Interviewers reward this comparison.
• Build the trie before writing the DFS — keep helper structures explicit.
• Mention leaf pruning as a "bonus optimisation" if time allows; it shows engineering taste.
• Discuss the trade-off of mutating the board vs using a visited set — both work, mutation is faster.
• If asked about thread safety, point out that mutating the board precludes parallelism; a visited set per thread fixes that.
• Confirm with the interviewer whether duplicate words may appear in words (LeetCode says no, but some variants allow it).

Follow-up Questions#

• What if words can be reused across cells? Drop the visited mark — but you would also need to bound recursion depth to prevent infinite loops.
• Diagonal movement allowed? Add four more directions; complexity becomes O(m times n times 8^L).
• What if the dictionary is streamed? Maintain the trie incrementally and re-run DFS on each new word — or batch updates.
• Return word coordinates instead of just the word? Track the path in the DFS frame and append it when you hit a terminal node.
• What about a 3D grid? Add a z-dimension, six neighbours; the trie + DFS pattern is identical.

Key Takeaways#

• A single trie unifies multi-pattern search on grids; it converts O(W) independent searches into O(1) amortised search per cell visit.
• The DFS state is the trie node, not the word; pruning happens automatically when a child is missing.
• Mark-and-restore backtracking on the board is faster than maintaining an external visited set.
• Leaf pruning by deleting empty subtrees is the difference between accepted and fast.
• This pattern transfers directly to log scanning, multi-keyword search engines, and DNA motif finding.
• Always build the trie once before the DFS loop, and always null out collected words to avoid duplicates.