4.15.3 — Word Search II

LeetCode 212 · Hard · ★ Blind 75

The problem

Given a grid of letters and a list of words, return every word that can be spelled by walking through adjacent cells (up, down, left, right). A cell cannot be used twice within one word.

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

→ ["oath", "eat"]

Up to a 12×12 grid and 30,000 words.

Why the obvious approach fails

Run the single-word search (LeetCode 79) once per word. Each run is $O(\text{cells} \times 4^L)$ , and with 30,000 words that is hopeless.

Name the waste precisely, because it points straight at the fix. Searching for "oath", "oats" and "oatmeal" walks the same o → a → t path three separate times. The words share prefixes, and the search does not know it.

A trie makes the words share those prefixes, so one walk explores all of them at once. That is the whole idea: put the words in a trie, then walk the grid once, moving through the trie as you go.

The pattern

Depth-first search from every cell, carrying a trie node alongside the position. At each step:

Look up the current letter among the trie node's children. If it is absent, this branch is dead — every word that could continue from here has been ruled out in one comparison. Stop.
If the node is marked as a word ending, record it.
Otherwise mark the cell as visited and try all four neighbours, then unmark it.

The trie is doing the pruning. Without it you explore the grid blindly; with it, a wrong letter kills the branch immediately.

Store the whole word on the terminal node. Instead of a boolean flag, put the word itself there. Then when you reach a word ending you can record it directly, with no need to have carried the letters along the path.

Set that field to None after recording. This prevents the same word being found twice from different starting cells, and it is cheaper than deduplicating a result list afterwards.

There is a further optimisation worth naming: after a word is found, prune the trie by removing leaf nodes with no children on the way back up. On adversarial inputs it makes a large difference. It is not required, and mentioning it is enough.

The solution

PythonTypeScript

python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None            # the whole word, not just a flag


class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = TrieNode()
        for word in words:
            node = root
            for c in word:
                node = node.children.setdefault(c, TrieNode())
            node.word = word

        rows, cols = len(board), len(board[0])
        result = []

        def dfs(r: int, c: int, node: TrieNode) -> None:
            letter = board[r][c]
            child = node.children.get(letter)
            if not child:                      # dead branch — prune immediately
                return

            if child.word:
                result.append(child.word)
                child.word = None              # do not report it twice

            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 < rows and 0 <= nc < cols and board[nr][nc] != '#':
                    dfs(nr, nc, child)
            board[r][c] = letter               # undo

        for r in range(rows):
            for c in range(cols):
                dfs(r, c, root)

        return result

class TNode {
  children = new Map<string, TNode>();
  word: string | null = null;
}

function findWords(board: string[][], words: string[]): string[] {
  const root = new TNode();
  for (const word of words) {
    let node = root;
    for (const c of word) {
      if (!node.children.has(c)) node.children.set(c, new TNode());
      node = node.children.get(c)!;
    }
    node.word = word;
  }

  const rows = board.length, cols = board[0].length;
  const result: string[] = [];

  function dfs(r: number, c: number, node: TNode): void {
    const letter = board[r][c];
    const child = node.children.get(letter);
    if (!child) return;

    if (child.word) {
      result.push(child.word);
      child.word = null;
    }

    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, child);
      }
    }
    board[r][c] = letter;
  }

  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      dfs(r, c, root);

  return result;
}

Marking the board itself is the visited set. Overwriting the cell with # costs nothing and needs no extra structure, and restoring it on the way out is the undo. This is the choose–recurse–undo shape from 4.8.4, with the board as the shared state.

Restoring the letter is not optional. Skip it and cells stay blocked for every later search, and words that exist go unfound. Note that the letter is saved in a local variable at the top, because by the time you restore it the board no longer holds it.

Do not return early after finding a word. A longer word may continue through the same cell — finding "oat" must not stop the search for "oath".

Checking the trie before descending is what makes it fast. The child lookup happens at the top of dfs, so a letter with no matching child ends the branch before any neighbour is considered.

Complexity

Building the trie is $O(\text{total characters in all words})$ .

The search is $O(\text{cells} \times 4 \times 3^{L-1})$ in the worst case, where L is the longest word — from each cell you have 4 directions initially and 3 thereafter, since you never step back onto the cell you came from.

That bound looks alarming and is almost never reached, because the trie cuts branches after one or two letters. The real behaviour is governed by how many prefixes actually exist in the grid.

Space is $O(\text{total characters})$ for the trie plus $O(L)$ for the recursion.

Where this goes next

Word Search (LeetCode 79) — one word, no trie needed. Do that one first if you have not.
Concatenated Words, Word Break II — a trie plus DFS over a string instead of a grid.
Boggle solvers — this exact algorithm, and it is what any real word-game program uses.

The rule: when many searches share prefixes, put the search targets in a trie and explore all of them in one traversal. The trie turns "try each word" into "try each path", and paths are far fewer.

What the interviewer will push on

"Why not run the single-word search for each word?" Repeated prefixes are rewalked once per word. The trie shares them.

"Where does the pruning happen?" The child lookup at the top of the DFS. A letter with no matching child ends the branch immediately.

"Why store the word on the node rather than a flag?" So you can record the result without carrying the path, and so you can null it to prevent duplicates.

"Why restore the board cell?" Otherwise cells stay blocked for later searches.

"Why not stop after finding a word?" A longer word may continue through the same cell.

"How would you optimise further?" Prune trie leaves after a word is found; also skip words containing letters the board does not have at all.

One thing to volunteer: name the waste in the naive approach before proposing the trie. "The words share prefixes and the naive search rewalks them once per word." That sentence is the reason the trie belongs here, and stating it first makes the solution look derived rather than recalled.

Next: 4.16 covers the heap — a tree that gives up full ordering to buy $O(1)$ access to the smallest element, and the array trick that means it needs no pointers at all.

4.15.3 — Word Search II ​

The problem ​

Why the obvious approach fails ​

The pattern ​

Two refinements that matter ​

The solution ​

Complexity ​

Where this goes next ​

What the interviewer will push on ​