Skip to main content

212. Word Search II

hardAsked at Uber

Given an m x n board of letters and a list of words, return all words that can be formed by adjacent cells (no reuse). Uber asks this to test trie + backtracking — running word-by-word DFS is too slow.

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

Source citations

Public interview reports confirming this problem appears in Uber loops.

  • Glassdoor (2026-Q1)— Uber L5 onsite reports include this as a recurring graph+trie hard.
  • Blind (2025-10)— Mentioned in Uber senior algorithm-track interviews.

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

Example 2

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

Approaches

1. Per-word DFS (LC 79 repeated)

For each word, run the Word Search I backtracking from every cell.

Time
O(W * m * n * 4^L)
Space
O(L)
function findWordsNaive(board, words) {
  const m = board.length, n = board[0].length;
  function dfs(i, j, w, k) {
    if (k === w.length) return true;
    if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] !== w[k]) return false;
    const tmp = board[i][j];
    board[i][j] = '#';
    const found = dfs(i + 1, j, w, k + 1) || dfs(i - 1, j, w, k + 1) || dfs(i, j + 1, w, k + 1) || dfs(i, j - 1, w, k + 1);
    board[i][j] = tmp;
    return found;
  }
  const result = [];
  for (const w of words) {
    let ok = false;
    for (let i = 0; i < m && !ok; i++) for (let j = 0; j < n && !ok; j++) if (dfs(i, j, w, 0)) ok = true;
    if (ok) result.push(w);
  }
  return result;
}

Tradeoff: Repeats the same DFS work across words sharing prefixes. With 3 * 10^4 words, this is far too slow. Mention before pivoting to the trie.

2. Trie + backtracking (optimal)

Build a trie of all words. DFS the board; at each cell, descend the trie. When a node has a word, record it (then null the word to dedupe). Prune children with no descendants.

Time
O(m * n * 4^L)
Space
O(total chars in words)
function findWords(board, words) {
  const root = {};
  for (const w of words) {
    let node = root;
    for (const c of w) {
      if (!node[c]) node[c] = {};
      node = node[c];
    }
    node.word = w;
  }
  const m = board.length, n = board[0].length;
  const result = [];
  function dfs(i, j, parent) {
    const c = board[i][j];
    const node = parent[c];
    if (!node) return;
    if (node.word) {
      result.push(node.word);
      node.word = null;
    }
    board[i][j] = '#';
    if (i + 1 < m && board[i + 1][j] !== '#') dfs(i + 1, j, node);
    if (i - 1 >= 0 && board[i - 1][j] !== '#') dfs(i - 1, j, node);
    if (j + 1 < n && board[i][j + 1] !== '#') dfs(i, j + 1, node);
    if (j - 1 >= 0 && board[i][j - 1] !== '#') dfs(i, j - 1, node);
    board[i][j] = c;
    if (Object.keys(node).length === 0) delete parent[c];
  }
  for (let i = 0; i < m; i++) for (let j = 0; j < n; j++) dfs(i, j, root);
  return result;
}

Tradeoff: Single board traversal that descends the trie once per cell. Pruning empty trie nodes makes repeated DFS converge fast. The 'null-the-word-after-find' trick dedupes the result list.

Uber-specific tips

Uber's bar here is explicitly stating why the trie beats per-word DFS. Say: 'Words share prefixes — if I check each word independently, I redo the same DFS over and over. A trie lets me explore the board once and descend the trie in lockstep.' Then mention the pruning: nodes with no remaining descendants can be deleted so future cells don't recurse into dead branches.

Common mistakes

  • Forgetting to null the word field after finding it (causes duplicate results).
  • Not pruning dead trie branches — slower but still correct.
  • Mutating the board to mark visited but forgetting to restore it after the DFS returns.

Follow-up questions

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

  • What if the same letter cell could be used twice in a word? (Different problem entirely.)
  • What if the grid is huge and the word list is small? (Per-word DFS might win in practice.)
  • Trie compression (radix tree) for very long shared prefixes.

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 mark cells with '#' and restore on backtrack?

Marking prevents re-visiting the same cell within a single DFS path. Restoring on backtrack means a different DFS path can still use the cell — only this path is blocked.

Is the pruning (delete empty children) necessary?

Not for correctness, but it dramatically speeds up the average case. Without it, exhausted branches still get visited by every cell.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →