Word Search

MediumBacktrackingArrayBacktrackingMatrixDFS

Problem

Given a 2D grid of letters and a target word, determine whether the word can be traced by moving between horizontally or vertically adjacent cells, without reusing any grid cell twice within the same trace.

Example. In a grid with rows ABCE, SFCS, ADEE, the word "ABCCED" can be traced from the top-left A, but "ABCB" cannot, since it would reuse the B cell already used earlier.

Key idea

This is a search-with-undo problem: match the word letter by letter from some starting cell, exploring up to four neighbors when the current letter matches, and backing out of dead ends. Because a used cell cannot be revisited within one attempt, correctness depends on marking cells visited during a path and unmarking them once that path is abandoned.

Try every cell as a starting point for the first letter. From a match, recurse toward each neighbor looking for the next letter, temporarily marking the current cell visited (for instance overwriting it with a sentinel character, then restoring it afterward) so recursion cannot loop back onto a cell already used. If a recursive call finds the full word, propagate success back up immediately; otherwise restore the cell and try the next direction. The search succeeds if any starting cell leads to a full match, and fails only once every cell and path is exhausted.

Solution

function exist(board: string[][], word: string): boolean {
  const rows = board.length;
  const cols = board[0].length;

  function search(row: number, col: number, index: number): boolean {
    if (index === word.length) {
      return true;
    }
    if (row < 0 || row >= rows || col < 0 || col >= cols) {
      return false;
    }
    if (board[row][col] !== word[index]) {
      return false;
    }

    const original = board[row][col];
    // Mark visited; '#' can't match a letter, so this cell can't be reused deeper in the path.
    board[row][col] = '#';

    // Stop trying further directions as soon as one leads to a full match.
    const found =
      search(row + 1, col, index + 1) ||
      search(row - 1, col, index + 1) ||
      search(row, col + 1, index + 1) ||
      search(row, col - 1, index + 1);

    // Restore the cell so sibling paths can still use it.
    board[row][col] = original;
    return found;
  }

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (search(row, col, 0)) {
        return true;
      }
    }
  }

  return false;
}

Complexity

  • Time: O(rows · cols · 4ᴸ), where L is the word length; from each starting cell, the search branches up to four ways at every letter.
  • Space: O(L). Recursion depth tracks how much of the word has been matched.

Watch out for

  • Restore the visited marker on backtrack, or an abandoned path leaves the grid corrupted for later attempts.
  • Bounds-check before every neighbor step; grid edges are the most common source of an out-of-range access.

Pattern

This is grid backtracking with in-place visited marking, the standard approach for path-tracing puzzles on a matrix. Number of Islands and Word Search II reuse the same neighbor-exploration structure, differing mainly in what marks progress and what ends the search.

Related questions