Backtracking · LC #79
Word Search
DFS+backtrack from each cell: temporarily mark the current cell as visited, explore all 4 directions for the next character, then restore the cell.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given an `m×n` grid of characters and a string `word`, return `true` if `word` exists in the grid via adjacent (4-directional) cells, visiting each cell at most once.
Sample I/O
Input: board=[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word="ABCCED" Output: true Input: same board, word="ABCB" Output: false (can't reuse B)
Intuition
How to Think About It
Intuition
Try starting from every cell that matches word[0]. From each valid start, recursively explore adjacent cells for the next character. The key constraint - no revisiting - is enforced by temporarily overwriting the cell with a sentinel.
Core Concept
For each cell (i,j): call dfs(i,j,0). dfs: if k==word.length return true. Bounds/char check. Mark board[i][j]='#'. Recurse all 4 directions with k+1. Restore board[i][j]. Return OR of all directions.
When to use
Path existence in a grid with constraints; any problem requiring 4/8-directional DFS with no revisit; maze solving.
When NOT to use
When you need the actual path (track visited list); when word length >> grid size (no path possible - can prune early); when multiple words needed simultaneously (use Trie + backtrack - Word Search II LC 212).
Key Insights
What to Know Cold
- In-place marking (cell = '#') avoids a separate visited array - O(1) extra space.
- Must restore the cell after recursion - this is the backtracking step.
- Check character match BEFORE marking to avoid marking then immediately returning false.
- Early termination: return true as soon as any path succeeds (short-circuit OR).
- Pruning: if remaining grid cells < remaining word length, prune immediately.
1 example
Worked Examples
Find "ABCCED" in character grid
Grid with mixed characters; locate "ABCCED" path.
DFS+backtrack from every matching first character.
Output: true for "ABCCED", false for "ABCB"
Grid DFS with backtracking is a core pattern for puzzle solvers, routing algorithms, and constraint-satisfaction problems.