Word Search

Problem

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

Examples

The brute-force approach

Try starting the word from every cell. From each starting cell, try all four directions recursively. Track visited cells so you don't reuse them.

for each cell (r, c):
    if dfs(board, r, c, word, 0, visited):
        return True
return False

Already the right approach. The key optimization is marking the current cell as visited in-place (overwrite with a sentinel) and restoring it after backtracking, instead of maintaining a separate visited set. This avoids O(m×n) extra memory per DFS call.

Spotting the pattern

This is a Backtracking problem. The key question to ask yourself:

How do you prevent the path from revisiting a cell it's currently using, without a separate visited array?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.