Skip to main content

27. Word Search II

hardAsked at Etsy

Find all words from a dictionary in a character grid — the trie-pruned DFS Etsy's search relevance team uses to match multi-word listing titles against buyer query tokens simultaneously.

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

Problem

Given an m x n board of characters and a list of strings words, return all words in the list that can be found in the board. Each word must be constructed from letters of sequentially adjacent cells (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 words[i] 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 = ["abdc","abcd"]
Output
["abdc"]

Approaches

1. Brute force: DFS per word

For each word, run a full DFS from every board cell. Correct but O(words.length * m * n * 4^L) where L is max word length. Too slow when the word list is large.

Time
O(W * m * n * 4^L)
Space
O(L) recursion stack
function findWords(board, words) {
  const m = board.length, n = board[0].length;
  const result = [];

  function dfs(r, c, word, idx) {
    if (idx === word.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n) return false;
    if (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) {
    for (let r = 0; r < m; r++) {
      for (let c = 0; c < n; c++) {
        if (dfs(r, c, word, 0)) { result.push(word); break; }
      }
    }
  }
  return result;
}

Tradeoff:

2. Trie + DFS with pruning

Insert all words into a trie. DFS from every cell, walking the trie simultaneously. When the trie child doesn't match the board cell, prune that path immediately. When a trie node's word field is set, record the word and clear it to avoid duplicates. Remove leaf nodes after a word is found to prune further.

Time
O(m * n * 4^L + W * L) — dramatic pruning in practice
Space
O(W * L) for the trie
function findWords(board, words) {
  // 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 m = board.length, n = board[0].length;
  const result = [];
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];

  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['$']) {
      result.push(next['$']);
      delete next['$'];
    }
    board[r][c] = '#';
    for (const [dr, dc] of dirs) dfs(r + dr, c + dc, next);
    board[r][c] = ch;
    // Prune: remove empty trie node
    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 result;
}

Tradeoff:

Etsy-specific tips

Etsy's search team navigates this pattern when matching multi-token buyer queries against a grid of listing-title characters. The trie version is the expected answer, but the pruning detail — removing trie nodes after all their words are found — is what separates a good answer from a great one. Make sure you explain why node deletion matters: it prevents the DFS from exploring subtrees that can no longer produce new words, cutting runtime significantly on dense word lists.

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

Practice these live with InterviewChamp.AI →