Skip to main content

212. Word Search II

hardAsked at DoorDash

Given a board and a list of words, return all words that can be formed by traversing adjacent cells. DoorDash uses this as a Trie + DFS combination — they want the trie-traversal speedup that beats naive per-word DFS.

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

Source citations

Public interview reports confirming this problem appears in DoorDash loops.

  • Glassdoor (2026-Q1)— DoorDash SWE onsite reports cite Word Search II for senior backend rounds.
  • Blind (2025-12)— DoorDash SDE2 reports note Trie as the algorithm DoorDash interviewers want by name.

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

Example 2

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

Approaches

1. Trie + DFS with pruning (optimal)

Build a Trie of all words. DFS each cell; descend the Trie alongside the board. When a Trie node has 'end', collect the word. Prune Trie leaves to speed later searches.

Time
O(m * n * 4^L)
Space
O(total chars in words)
function findWords(board, words) {
  function buildTrie() {
    const root = {};
    for (const word of words) {
      let node = root;
      for (const ch of word) {
        if (!node[ch]) node[ch] = {};
        node = node[ch];
      }
      node.word = word;
    }
    return root;
  }
  const root = buildTrie();
  const result = [];
  const m = board.length, n = board[0].length;
  function dfs(r, c, node) {
    const ch = board[r][c];
    const next = node[ch];
    if (!next) return;
    if (next.word) {
      result.push(next.word);
      next.word = null; // dedupe
    }
    board[r][c] = '#';
    const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] !== '#') {
        dfs(nr, nc, next);
      }
    }
    board[r][c] = ch;
    if (Object.keys(next).length === 0) delete node[ch]; // prune leaf
  }
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      dfs(r, c, root);
    }
  }
  return result;
}

Tradeoff: DoorDash's expected answer. Trie shares the prefix walk across all words, and pruning leaves makes later DFS calls faster. Dedupe via clearing node.word.

2. Per-word DFS (Word Search I, repeated)

For each word, run a Word Search I DFS over the board.

Time
O(W * m * n * 4^L)
Space
O(L)
function findWordsBrute(board, words) {
  const m = board.length, n = board[0].length;
  const result = [];
  function exist(word) {
    function dfs(r, c, i) {
      if (i === word.length) return true;
      if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== word[i]) return false;
      const ch = board[r][c];
      board[r][c] = '#';
      const found = dfs(r+1, c, i+1) || dfs(r-1, c, i+1) || dfs(r, c+1, i+1) || dfs(r, c-1, i+1);
      board[r][c] = ch;
      return found;
    }
    for (let r = 0; r < m; r++) {
      for (let c = 0; c < n; c++) {
        if (dfs(r, c, 0)) return true;
      }
    }
    return false;
  }
  for (const word of words) {
    if (exist(word)) result.push(word);
  }
  return result;
}

Tradeoff: W * board * 4^L = expensive when words share prefixes. DoorDash interviewers want you to NAME this approach, then derive Trie.

DoorDash-specific tips

DoorDash interviewers grade on whether you NAME TRIE early. State: 'building a Trie lets all words with the same prefix share a single DFS walk' BEFORE coding. The leaf-pruning step is the senior signal.

Common mistakes

  • Forgetting to backtrack the board mutation — leaves the '#' marker and breaks later searches.
  • Inserting the word at end-of-Trie without a flag — must use node.word or a boolean.
  • Not deduping the result — same word can be reachable from multiple starting cells.

Follow-up questions

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

  • Word Search (LC 79) — single word, no Trie needed.
  • Word Break (LC 139) — DP variant with a dictionary.
  • Word Squares (LC 425) — Trie-driven backtracking.

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 prune Trie leaves?

After a word is found, its leaf has no further children to explore. Removing it from the parent's children means future DFS won't even descend into it.

Why mark board cells with '#'?

To prevent revisiting in the current path. Restore on backtrack so other DFS paths can still use the cell.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →