Word Search

You are given a grid of letters board (a list of rows, each cell a one-character string) and a string word.

Decide whether word can be traced through the grid. A trace starts at any cell whose letter matches the first character of word, and each following character must be in a cell that shares a side (up, down, left or right) with the previous one. Diagonal steps are not allowed, and a single cell may be used at most once within one trace.

Return true if such a trace exists, otherwise false.

Example 1

Example 2

Example 3

Constraints

• 1 <= board.length, board[i].length <= 6
• 1 <= word.length <= 15
• board and word contain only English letters (upper and lower case are different)

Pattern Path · Backtracking · problem 123 of 169

Start simple

Enumerate every simple path of length L in the grid and compare it with the word: hopelessly exponential without pruning on mismatched letters.

The key idea

Run a depth-first search from every cell. The search state is a cell (r, c) and an index i meaning "word[0..i-1] has been matched and word[i] should be at (r, c)".

• If the cell is outside the grid or its letter differs from word[i], this branch fails immediately. This is the pruning that keeps the search practical: most branches die after a step or two.
• If i is the last index, the whole word has been matched.
• Otherwise, temporarily overwrite the cell with a marker such as # so the path cannot step on it again, recurse into the four neighbours with i + 1, then put the letter back.

Restoring the letter is what makes this backtracking: a cell used by a failed path is free again for later paths that might reach it from a different direction.

Before searching, compare letter counts of the word with the board. If the board lacks enough copies of a letter, no search can succeed, which removes the worst cases such as a board full of A and a word ending in B. Starting from the rarer end of the word is another common trick.

Complexity

• Time: O(m · n · 3^L)
• Space: O(L) recursion depth

Python

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])

        # Quick rejection: the board must hold enough copies of every letter.
        available = Counter(ch for row in board for ch in row)
        if Counter(word) - available:
            return False

        def dfs(r, c, i):
            if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]:
                return False
            if i == len(word) - 1:
                return True
            board[r][c] = "#"  # mark as used on the current path
            found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1) or
                     dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
            board[r][c] = word[i]  # restore for other paths
            return found

        return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

JavaScript

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

  // Quick rejection: the board must hold enough copies of every letter.
  const available = new Map();
  for (const row of board) for (const ch of row) available.set(ch, (available.get(ch) || 0) + 1);
  for (const ch of word) {
    const left = (available.get(ch) || 0) - 1;
    if (left < 0) return false;
    available.set(ch, left);
  }

  const dfs = (r, c, i) => {
    if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[i]) return false;
    if (i === word.length - 1) return true;
    board[r][c] = '#'; // mark as used on the current path
    const found = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1) ||
                  dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1);
    board[r][c] = word[i]; // restore for other paths
    return found;
  };

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
  return false;
};

What the interviewer is checking

The interviewer wants a correct grid DFS with clean bounds checks and, above all, correct handling of the visited state when backtracking.

Mistakes to avoid

• Keeping a global visited set but never un-marking cells when a branch fails, which wrongly blocks other paths.
• Allowing the same cell to be used twice, e.g. spelling ABA from just two cells.
• Checking bounds after indexing into the grid instead of before.

Follow-ups to expect

• How would you find all words from a large dictionary at once? (Trie plus one grid DFS.)
• How would you prune harder on adversarial boards? (Letter counts, search from rarer end.)
• What if diagonal moves were allowed? (Eight neighbours, branching factor 7.)

In real software

Word puzzle games and their solvers use this search, and the same mark-explore-unmark pattern appears in path finding with no-revisit rules, such as routing through a circuit grid.

Practice next