79. Word Search

Quick Identifier

Topic: backtracking
Pattern: DFS / Backtracking
Difficulty: Medium
Companies: Amazon, Meta, Microsoft, Google, Apple
Frequency: Very High
LeetCode: 79

Quick Sights

Time Complexity: O(n * m * 4^L) from the optimal approach.
Space Complexity: O(recursion depth) excluding the final output unless stated.
Core Mechanism: In a 2D grid of letters, determine if word exists as a path moving up/down/left/right using each cell at most once per path.

Concept Explanation

In a 2D grid of letters, determine if word exists as a path moving up/down/left/right using each cell at most once per path.

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

Path in grid with visit once constraint
Backtrack after failed branch — mark visited, recurse, unmark
Word length × board size bounds search

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

BFS per start — harder for full word (path state explosion).
Optimal — DFS from each cell matching prefix — O(n * m * 4^L) worst.

Optimal Solution

Go

func exist(board [][]byte, word string) bool {
	rows := len(board)
	cols := len(board[0])

	var dfs func(row int, col int, position int) bool
	dfs = func(row int, col int, position int) bool {
		if position == len(word) {
			return true
		}
		if row < 0 || col < 0 || row >= rows || col >= cols {
			return false
		}
		if board[row][col] != word[position] {
			return false
		}
		temp := board[row][col]
		board[row][col] = '#'
		found := dfs(row+1, col, position+1) ||
			dfs(row-1, col, position+1) ||
			dfs(row, col+1, position+1) ||
			dfs(row, col-1, position+1)
		board[row][col] = temp
		return found
	}

	for row := 0; row < rows; row++ {
		for col := 0; col < cols; col++ {
			if dfs(row, col, 0) {
				return true
			}
		}
	}
	return false
}

JavaScript

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

  function dfs(row, col, position) {
    if (position === word.length) {
      return true;
    }
    if (row < 0 || col < 0 || row >= rows || col >= cols) {
      return false;
    }
    if (board[row][col] !== word[position]) {
      return false;
    }
    const temp = board[row][col];
    board[row][col] = '#';
    const found =
      dfs(row + 1, col, position + 1) ||
      dfs(row - 1, col, position + 1) ||
      dfs(row, col + 1, position + 1) ||
      dfs(row, col - 1, position + 1);
    board[row][col] = temp;
    return found;
  }

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