DSA AnimatorDSA animations
Word Search LC #79 Medium DFS Backtracking
Problem

Given an m×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 (horizontally or vertically). The same letter cell may not be used more than once.

Example 1
Input: board=[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word="ABCCED"
Output: true
Explanation: A(0,0)→B(0,1)→C(0,2)→C(1,2)→E(2,2)→D(2,1)
Example 2
Input: word="SEE"
Output: true
Explanation: S(1,3)→E(2,3)→E(2,2)
Example 3
Input: word="ABCB"
Output: false
Explanation: Cannot reuse B at (0,1).
Constraints: 1 ≤ m, n ≤ 6  |  1 ≤ word.length ≤ 15  |  board and word consist of uppercase English letters.
Try Examples
Custom:
Approach
DFS Backtracking: try each cell as start, explore all 4 directions
Mark cell visited (temp replace with '#'), recurse, then unmark (backtrack). O(m×n×4L)
Word Progress
Board
Variables
r
—
c
—
k (index)
—
word[k]
—
found
—
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Scan every cell; if board[r][c] == word[0], launch DFS from it
2
DFS base case: k == word.length → full match, return true
3
Bounds / mismatch / visited ('#') check → return false
4
Mark cell with '#', recurse 4 directions (↓↑→←), then restore original char
5
If no start succeeds → return false
Time
O(m·n·4L)
Space
O(L)
Why Backtracking Works

We explore every possible path depth-first. Marking the current cell as visited ('#') prevents revisiting it in the same path. When we backtrack (restore the cell), that cell becomes available again for other paths — ensuring correctness without extra space for a visited array.

How to solve Word Search

LeetCode 79 · Medium · Matrix · Pattern: Backtracking DFS

Why the obvious approach is slow

Listing every path in the grid is exponential and wasteful. We only need to follow paths that keep matching the word.

The key idea

Try each cell as a starting point. From a cell that matches the current letter, explore its four neighbours for the next letter. Mark the cell as used while exploring, and unmark it when you come back, which is backtracking.

Remember

DFS plus mark and unmark is backtracking on a grid. Stop early as soon as a letter does not match.

Run the animation above on your own input, or watch the 1:26 video explanation of Word Search with a dry run and Java code.

More Matrix problems