← Back to DSA Animator
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.