Skip to main content

212. Word Search II

hardAsked at Airbnb

Given an m x n board of letters and a list of words, return all words formed by adjacent cells (no reuse). Airbnb asks this to test trie + DFS — running word-by-word DFS doesn't scale.

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

Source citations

Public interview reports confirming this problem appears in Airbnb loops.

  • Glassdoor (2026-Q1)— Airbnb senior+ onsite reports include this as a recurring graph+trie hard.
  • Blind (2025-11)— Mentioned in Airbnb L5 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)

Run Word Search I backtracking once per word 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 identical DFS work across words with shared prefixes. With 3 * 10^4 words this times out. Mention as a stepping stone, then pivot.

2. Trie + backtracking (optimal)

Build a trie of all words. DFS the board, descending the trie in lockstep. Record a word when you hit a node with one stored. Prune empty branches.

Time
O(m * n * 4^L)
Space
O(total chars)
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 walking the trie in lockstep. Pruning dead trie branches makes the average case fast.

Airbnb-specific tips

Airbnb wants you to articulate the per-word DFS is wasteful because words share prefixes — a trie lets you walk the board once and descend the trie in lockstep. State that out loud before reaching for the trie code. Pruning is the bonus: empty nodes can be deleted so future cells don't recurse into dead branches.

Common mistakes

  • Forgetting to null the word after finding it (causes duplicate results).
  • Not pruning dead trie branches — slower but still correct.
  • Mutating the board and forgetting to restore on backtrack.

Follow-up questions

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

  • What if a single cell could be reused within a word? (Different problem entirely.)
  • What if the grid is huge and the word list is small? (Per-word DFS might be faster in practice.)
  • Radix-tree compression for 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 '#' and restore on backtrack?

Marking prevents re-visiting on this DFS path. Restoring allows a different path to use the cell.

Is pruning necessary?

Not for correctness, but dramatically speeds up the average case by skipping exhausted branches.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →