loading

Word Search — Step-by-Step Visualization

mediumLeetCode #79ArrayBacktrackingMatrix

Given an `m x n` grid of characters `board` and a string `word`, return `true` if `word` exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Algorithm Pattern

Backtracking (DFS)

Key Idea

We iterate through every cell in the board to find a starting character that matches the first letter of the word. From there, we perform a Depth-First Search (DFS) in all four directions, keeping track of visited cells in the current path. If a path fails to match the word, we backtrack by unmarking the current cell so it can be used in other paths.

Step-by-Step Approach

  1. Iterate through every row `r` and column `c` on the board.
  2. If `board[r][c] == word[0]`, start a recursive `dfs(r, c, 0)` call.
  3. Base Case: If `index == word.length`, we found the word! Return `true`.
  4. Boundary Checks: Ensure `r, c` are within the grid and `board[r][c] == word[index]`.
  5. Recursive Step: Temporarily mark `board[r][c]` as visited (e.g., replace with `#`).
  6. Explore four adjacent directions (Up, Down, Left, Right).
  7. Backtrack: Restore `board[r][c]` before returning from the recursion.

Common Gotchas

  • Don't forget to restore the cell character after the recursive calls (backtracking).
  • Ensure the base case check happens at the very beginning of the DFS to handle the single-character word case or the final character match.

Related Problems

← All problems