Skip to main content

30. Word Search II

hardAsked at Meta

Find all dictionary words on a 2D character board — Meta's AR text-recognition and content-moderation grid scanners use trie-backed DFS to match thousands of patterns simultaneously without redundant board traversals.

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 found on the board. Words can be constructed from adjacent (horizontally or vertically) cells and each cell may be used only once per 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
  • words[i].length is between 1 and 10

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 = ["abcd"]
Output
[]

Approaches

1. DFS per word (brute force)

For each word, run a DFS from every cell. Works but repeats traversal for shared prefixes across words.

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

Tradeoff:

2. Trie + DFS (optimal)

Build a trie from the word list. DFS from each cell traversing the trie simultaneously. Prune dead branches early; remove matched words from the trie to avoid duplicates.

Time
O(m * n * 4 * 3^(L-1))
Space
O(total chars in words)
function findWords(board, words) {
  const m = board.length, n = board[0].length;
  const root = {};
  for (const w of words) {
    let node = root;
    for (const c of w) { if (!node[c]) node[c] = {}; node = node[c]; }
    node['$'] = w;
  }
  const res = [];
  function dfs(r, c, node) {
    if (r<0||r>=m||c<0||c>=n) return;
    const ch = board[r][c];
    if (ch === '#' || !node[ch]) return;
    const next = node[ch];
    if (next['$']) { res.push(next['$']); delete next['$']; }
    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;
    if (Object.keys(next).length === 0) delete node[ch];
  }
  for (let r=0;r<m;r++) for (let c=0;c<n;c++) dfs(r,c,root);
  return res;
}

Tradeoff:

Meta-specific tips

Meta considers this a top-tier problem distinguishing senior candidates. The key insight is that building a trie up front amortizes the prefix-matching cost across all words. Mention the pruning optimization — delete matched words from the trie and prune empty nodes — it is the difference between a timeout and a pass at Meta's scale. Always ask whether you can mutate the board; marking visited cells in-place avoids an extra visited matrix.

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 Meta interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →