Word Search II

The problem

m × n board of letters and a list of words. Return all words that can be formed by adjacent (4-dir) letters without reusing a cell in one word. Same as Word Search but many words.

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"]

Brute force

Run Word Search I for each word independently. O(words · m · n · 4^L) — too slow when word list is large.

Optimal: Trie + board DFS

1. Insert all words into a trie.
2. DFS from every cell; walk trie in parallel.
3. When a node marks word end, record it (and optionally clear to avoid dupes).
4. Prune empty trie branches.

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

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

  const rows = board.length;
  const cols = board[0].length;
  const res: string[] = [];
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];

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

    if (next.word) {
      res.push(next.word);
      next.word = null; // dedupe
    }

    board[r][c] = "#";
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
      if (board[nr][nc] === "#") continue;
      dfs(nr, nc, next);
    }
    board[r][c] = ch;

    // optional prune
    if (next.children.size === 0) node.children.delete(ch);
  }

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

Time	O(m · n · 4 · 3^{L-1}) worst board search shared across trie
Space	O(total characters in words)

Edge cases

• Empty words / empty board
• Duplicate words in list
• Word longer than board cells
• Overlapping paths for different words

Common bugs

• Not restoring board cell after DFS
• Forgetting to dedupe found words
• Building trie wrong (shared prefixes mishandled)
• 8-directional neighbors

Interview delivery

1. Many words → trie, not N× search.
2. DFS board + trie node.
3. Mark visited with mutation.
4. Prune / dedupe.
5. Contrast with Word Search I.

Related

• Word Search
• Implement Trie
• Word Ladder
• Number of Islands

Further reading

• LeetCode 212 — Word Search II
• Trie