Word Search Grid Backtracking DSA Solution

Learning Outcome

After this lesson, you should be able to mark a grid cell as used during one path and restore it for future paths.

Problem Statement

Given a board and a word, return true if the word exists by moving horizontally or vertically through adjacent cells without reusing a cell.

Input	Output	Why
`board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"`	`true`	A path A -> B -> C -> C -> E -> D exists using adjacent cells.

Brute Force Approach

Generate paths without checking the next required character early. This explores too many impossible paths.

Optimized Approach

Start DFS from every matching cell. Stop on boundary, mismatch, or reused cell, and restore the cell after exploring.

Exact Pseudocode

exists(row, col, index):
  if index == word.length:
    return true
  if out of bounds or board[row][col] != word[index]:
    return false
  save cell and mark used
  found = search four neighbors for index + 1
  restore cell
  return found

for each cell:
  if exists(cell, 0):
    return true
return false

Reference Code

class Solution:
    def exist(self, board, word):
        rows, cols = len(board), len(board[0])

        def dfs(r, c, i):
            if i == len(word):
                return True
            if r < 0 or c < 0 or r == rows or c == cols or board[r][c] != word[i]:
                return False

            saved = board[r][c]
            board[r][c] = "#"
            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] = saved
            return found

        for r in range(rows):
            for c in range(cols):
                if dfs(r, c, 0):
                    return True
        return False

Sample Dry Run

Step	State	Result
Start A	board[0][0] matches word[0]	Mark A used
Move to B	Right neighbor matches word[1]	Continue path
Continue C,C,E,D	Each step matches next character	index reaches word length
Return	Base case true	Word exists

Complexity

Measure	Value	Reason
Time	O(rows * cols 4^wordLength)	Each cell can start a DFS and each step can branch up to four ways.
Space	O(wordLength)	The recursion depth is at most the word length.

Measure

Value

Reason

Time

O(rows * cols

4^wordLength)

Each cell can start a DFS and each step can branch up to four ways.

Space

O(wordLength)

The recursion depth is at most the word length.

Edge Cases

The same cell cannot be reused in one path.
Only horizontal and vertical moves are allowed.
Restore the cell after each path attempt.

Interview Checklist

Check boundary and character mismatch before marking.
Mark the current cell as used for this path.
Restore the cell before returning.

FAQs

Why restore the cell?

The same cell may be needed in a different path starting elsewhere.

Why mark in-place?

It avoids an extra visited matrix while still preventing reuse in the current path.

What is the core pattern?

Grid backtracking with temporary marking.

Word Search: Grid Backtracking Pattern