Word Search II

HardTriesArrayTrieBacktrackingMatrix

Problem

You are given a grid of letters and a list of words. Find every word from the list that can be traced as a path through adjacent grid cells (up, down, left, right), reusing no cell within a single word's path, and return all words from the list that can be found this way.

Example. On a grid containing the letters to spell "oath" and "eat" along adjacent cells, both words would be returned if their letter paths exist, while a word like "pea" is excluded if no adjacent path spells it.

Key idea

Searching for each word independently means a fresh grid exploration per word, repeating the same work over and over. That is wasteful when several words share starting letters. The fix is to search for all words at once: combine the dictionary into a single trie, then walk the grid once, following trie edges instead of chasing one target word.

Start a depth-first search from every cell. At each step, check whether the current letter has a matching child in the trie; if not, the path cannot spell any dictionary word and stops there. If it does, move to that child, mark the cell visited so the path cannot revisit it, and explore the neighbors. Whenever the current trie node marks a completed word, record it. Because branches sharing a prefix are explored together, the search prunes as soon as a partial path stops matching any word.

Solution

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  word: string | null = null; // set to the full word at the node where it ends
}

function buildTrie(words: string[]): TrieNode {
  const root = new TrieNode();
  for (const word of words) {
    let node = root;
    for (const char of word) {
      let child = node.children.get(char);
      if (!child) {
        child = new TrieNode();
        node.children.set(char, child);
      }
      node = child;
    }
    node.word = word;
  }
  return root;
}

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

  const dfs = (row: number, col: number, node: TrieNode): void => {
    if (row < 0 || row >= rows || col < 0 || col >= cols) {
      return;
    }

    const char = board[row][col];
    if (char === '#') {
      return; // cell is already used by the current path
    }

    const child = node.children.get(char);
    if (!child) {
      return;
    }

    if (child.word !== null) {
      found.push(child.word);
      child.word = null; // avoid returning the same word twice
    }

    board[row][col] = '#'; // mark visited for this path
    dfs(row + 1, col, child);
    dfs(row - 1, col, child);
    dfs(row, col + 1, child);
    dfs(row, col - 1, child);
    board[row][col] = char; // unmark on backtrack so other paths can reuse the cell
  };

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

  return found;
}

Complexity

  • Time: O(rows × cols × 4^maxLen) in the worst case, where maxLen is the longest word, since each cell can start a bounded-depth backtracking search; trie pruning cuts this substantially in practice.
  • Space: O(total characters in the dictionary) for the trie, plus O(maxLen) recursion depth.

Watch out for

  • Unmark a visited cell after backtracking out of it, or later paths through that cell will be wrongly blocked.
  • Avoid returning the same word twice; once found, removing or flagging its trie ending prevents duplicate matches from overlapping paths.

Pattern

This pairs grid backtracking with a shared trie, a pattern for any problem that checks a grid against many target patterns at once rather than one at a time; the same combination shows up in boggle-style word games and multi-pattern string matching.

Related questions