Skip to main content

212. Word Search II

hardAsked at Google

Given a 2D board and a list of words, return all words on the board. Google asks this to test whether you reach for a trie + DFS combo and can articulate why it's drastically faster than running Word Search I once per word.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Google L4/L5 onsite reports cite this as the trie-application round.
  • Blind (2025-09)— Recurring Google interview problem for senior IC roles.

Problem

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

Constraints

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

Examples

Example 1

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

Approaches

1. Run Word Search I per word

For each word, run the single-word DFS from every cell.

Time
O(W * m * n * 4^L)
Space
O(L)
// Run a standard DFS exists() per word — outlined, not coded.
// For W = 30000 words and L = 10, this is impractical.

Tradeoff: Restarts DFS from scratch for every word; redundant work because many words share prefixes. Mention only as the anti-pattern.

2. Trie + single DFS pass (optimal)

Build a trie of all words. DFS from every cell, descending the trie in lockstep with the path. Emit + prune words as you find them.

Time
O(m * n * 4^L)
Space
O(total word characters)
class TrieNode {
  constructor() { this.children = {}; this.word = null; }
}

function buildTrie(words) {
  const root = new TrieNode();
  for (const w of words) {
    let node = root;
    for (const ch of w) {
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch];
    }
    node.word = w;
  }
  return root;
}

function findWords(board, words) {
  const root = buildTrie(words);
  const m = board.length, n = board[0].length;
  const result = [];
  function dfs(i, j, node) {
    const ch = board[i][j];
    const child = node.children[ch];
    if (!child) return;
    if (child.word) {
      result.push(child.word);
      child.word = null; // prune to avoid duplicates
    }
    board[i][j] = '#';
    const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
    for (const [di, dj] of dirs) {
      const ni = i + di, nj = j + dj;
      if (ni >= 0 && ni < m && nj >= 0 && nj < n && board[ni][nj] !== '#') {
        dfs(ni, nj, child);
      }
    }
    board[i][j] = ch;
    // optional optimization: prune empty trie subtrees
    if (Object.keys(child.children).length === 0) delete node.children[ch];
  }
  for (let i = 0; i < m; i++) for (let j = 0; j < n; j++) dfs(i, j, root);
  return result;
}

Tradeoff: Single board traversal regardless of how many words share prefixes. The trie collapses overlapping work; pruning empty subtrees keeps the DFS fast.

Google-specific tips

Google interviewers want the trie-pruning optimization. After finding a word, set its node.word = null AND optionally prune empty subtrees from the parent. Without pruning, you'll re-explore dead trie branches. The L4+ bar at Google is articulating both optimizations.

Common mistakes

  • Forgetting to mark/unmark visited cells (causes the same cell to be reused in a word).
  • Adding the same word to result multiple times (forgot to null the trie node after finding).
  • Not pruning empty trie subtrees, leading to wasted DFS work.

Follow-up questions

An interviewer at Google may pivot to one of these next:

  • What if words could be reused (cells can be visited multiple times in one word)?
  • What if the board is huge but the word list is short? (Trie still wins.)
  • What if you needed the cell-path for each found word?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the trie + single-pass faster than per-word DFS?

If 1000 words start with 'abc', per-word DFS re-walks 'abc' 1000 times. The trie walks it once and branches only when the words diverge.

Is the pruning step necessary?

Not for correctness, but it can be 10x faster on large word lists. Once a trie branch has no leaves left, you don't want to keep descending it.

Practice these live with InterviewChamp.AI

Drill Word Search II and other Google interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →