Word Search II

Examples

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

"oath" traces down the first column then right along row 2 (o-a-t-h). "eat" traces e-a-t using cells from rows 1-2. "pea" and "rain" can't be traced through any adjacent path in this grid.

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

"abcb" would need to revisit the "b" cell, which isn't allowed within a single word's path.

Constraints

• 1 <= board rows, columns <= 12

• board[i][j] is a lowercase English letter

• 1 <= words.length <= 3 * 10^4

• 1 <= words[i].length <= 10

• All words are unique

Approach

Searching the grid separately for each word (brute force) means redoing a lot of the same exploration, since many words share prefixes. Instead, build a single trie out of the entire word list first.

Then do one DFS from every cell in the grid. At each step, only continue into a neighboring cell if the current trie node has a child for that cell's letter - the trie prunes the search the moment the letters-so-far stop being a prefix of any word. Whenever the trie node reached is marked as a complete word, that word has been found. Cells already used in the current path are temporarily marked so they aren't reused, then unmarked ("backtracked") once that branch of exploration is done.

A couple of practical optimizations keep this fast: once a word is found, remove it from consideration in the trie so it isn't rediscovered repeatedly, and prune trie nodes that have no children left.

Solutions

Brute Force - DFS per Word

For each word independently, try starting a DFS/backtracking search from every cell in the grid, checking whether that word's exact letter sequence can be traced out.

function findWords(board, words) {
  const rows = board.length;
  const cols = board[0].length;
  const found = [];

  function dfs(r, c, word, i) {
    if (i === word.length) return true;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (board[r][c] !== word[i]) return false;

    const temp = board[r][c];
    board[r][c] = "#"; // mark as visited for this path

    const result =
      dfs(r + 1, c, word, i + 1) ||
      dfs(r - 1, c, word, i + 1) ||
      dfs(r, c + 1, word, i + 1) ||
      dfs(r, c - 1, word, i + 1);

    board[r][c] = temp; // backtrack
    return result;
  }

  for (const word of words) {
    let ok = false;
    for (let r = 0; r < rows && !ok; r++) {
      for (let c = 0; c < cols && !ok; c++) {
        if (dfs(r, c, word, 0)) ok = true;
      }
    }
    if (ok) found.push(word);
  }

  return found;
}

Time: O(W * rows * cols * 4^L), where W is the number of words and L is the max word length - each word triggers its own full grid search · Space: O(L) recursion depth per search

Optimal - Trie + Combined DFS

Build one trie from all the words. Do a single DFS pass over the grid that walks down the trie in step with the grid path, so shared prefixes across words are explored only once. Mark a word as found the instant its trie node is reached.

class TrieNode {
  constructor() {
    this.children = new Map();
    this.word = null; // stores the full word when this node completes one
  }
}

function findWords(board, words) {
  const root = new TrieNode();

  // Build the trie from every word in the list.
  for (const word of words) {
    let node = root;
    for (const ch of word) {
      if (!node.children.has(ch)) {
        node.children.set(ch, new TrieNode());
      }
      node = node.children.get(ch);
    }
    node.word = word;
  }

  const rows = board.length;
  const cols = board[0].length;
  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.children.has(ch)) return;

    const next = node.children.get(ch);
    if (next.word !== null) {
      result.push(next.word);
      next.word = null; // avoid pushing the same word again
    }

    board[r][c] = "#"; // mark visited for this path

    dfs(r + 1, c, next);
    dfs(r - 1, c, next);
    dfs(r, c + 1, next);
    dfs(r, c - 1, next);

    board[r][c] = ch; // backtrack

    // Prune dead trie branches so future searches skip them faster.
    if (next.children.size === 0) {
      node.children.delete(ch);
    }
  }

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

  return result;
}

Time: O(rows * cols * 4 * 3^(L-1)) roughly - one combined DFS over the grid guided by the trie, where L is the max word length, versus a separate search per word · Space: O(N) for the trie (N = total letters across all words), plus O(L) recursion depth