Skip to main content

212. Word Search II

hardAsked at Duolingo

Find all words from a dictionary that exist as paths in a letter grid — the trie-pruned DFS that Duolingo's word-puzzle feature uses to validate which target vocabulary words a learner can trace through a randomly generated tile board in one traversal.

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

Problem

Given an m x n board of characters and a list of words, return all words that can be constructed from letters of sequentially adjacent cells (horizontally or vertically). The same cell may not be used more than once in constructing a single word.

Constraints

  • m == board.length, n == board[i].length
  • 1 <= m, n <= 12
  • 1 <= words.length <= 3 * 10^4
  • 1 <= words[i].length <= 10
  • All characters are lowercase English letters
  • All words in 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. Brute force — run Word Search I for each word

For each word, perform an independent DFS from every board cell — O(words * m * n * 4^L) total.

Time
O(W * m * n * 4^L) where W = words, L = max word length
Space
O(L) stack depth
function findWords(board, words) {
  const rows = board.length;
  const cols = board[0].length;

  function exists(word) {
    function dfs(r, c, idx) {
      if (idx === word.length) return true;
      if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
      if (board[r][c] !== word[idx]) return false;
      const tmp = board[r][c];
      board[r][c] = '#';
      const found = dfs(r+1,c,idx+1) || dfs(r-1,c,idx+1) ||
                    dfs(r,c+1,idx+1) || dfs(r,c-1,idx+1);
      board[r][c] = tmp;
      return found;
    }
    for (let r = 0; r < rows; r++) {
      for (let c = 0; c < cols; c++) {
        if (dfs(r, c, 0)) return true;
      }
    }
    return false;
  }

  return words.filter(exists);
}

Tradeoff:

2. Optimal — trie-pruned DFS with word deletion

Build a trie from all words; DFS each board cell and descend the trie simultaneously, pruning branches and deleting matched words to avoid revisiting.

Time
O(m * n * 4 * 3^(L-1)) with pruning
Space
O(W * L) trie + O(L) stack
function findWords(board, words) {
  const rows = board.length;
  const cols = board[0].length;

  // Build trie
  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;
  }

  const result = [];

  function dfs(r, c, node) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    const ch = board[r][c];
    if (ch === '#' || !node[ch]) return;
    const next = node[ch];
    if (next['$']) {
      result.push(next['$']);
      delete next['$'];  // avoid duplicate results
    }
    board[r][c] = '#';
    dfs(r+1, c, next);
    dfs(r-1, c, next);
    dfs(r, c+1, next);
    dfs(r, c-1, next);
    board[r][c] = ch;
    // Prune empty trie nodes to speed up future traversals
    if (Object.keys(next).length === 0) delete node[ch];
  }

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

  return result;
}

Tradeoff:

Duolingo-specific tips

This is one of Duolingo's most cited hard interview problems because it combines two of their core product primitives: the trie (dictionary lookup) and grid path-finding (tile puzzles). Interviewers grade on two things: whether you build the trie once rather than per word, and whether you prune empty trie nodes after matching to stop re-traversing branches that are already exhausted. Verbalize the pruning step before coding — it is the key optimization and many candidates miss it. A common follow-up: 'How do you handle the case where words share prefixes?' — the trie handles this naturally; walk through an example showing two words diverging at a node.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →