DSA Tracker

Visualize

Word Search

The core idea: treat every cell as a potential start of the word and explore outward only in directions where the next letter still matches — that's DFS with backtracking. A cell gets temporarily marked visited so the same cell can't be reused twice within one path (a letter can't do double duty), but the moment a path dead-ends, un-marking it frees that cell for other paths that start elsewhere. That mark-then-unmark discipline is what lets one exhaustive search safely try every route without a cell used on one failed path blocking a different path that never touched it.

Details

Animated on: 3x3 board with letters, find word "ABCCED" which exists as a path.

Problem:Word SearchMedium

Pattern:Backtracking with Constraints

Matrix

step 1 / 8

A
[0]
B
[1]
C
[2]
S
[3]
F
[4]
C
[5]
A
[6]
D
[7]
E
[8]

Step 1: Start DFS at (row=0,col=0), flattened idx=0. Board[0][0]='A' matches word[0]='A'. Mark visited, look for 'B' (word[1]).

  • cur=0· arr[0] = A
Pseudocode
1FUNCTION exist(board, word):
2  n = number of rows, m = number of columns
3  visited = a grid of false flags, one per cell
4  FUNCTION dfs(r, c, k):
5    IF k equals the length of word: RETURN true (whole word matched)
6    IF (r,c) is out of bounds, or already visited, or board[r][c] != word[k]: RETURN false
7    mark (r,c) as visited
8    res = try dfs into the up, down, left, right neighbors with k+1 (true if any succeeds)
9    un-mark (r,c) as visited (backtrack)
10    RETURN res
11  FOR each row i:
12    FOR each column j:
13      IF dfs(i, j, 0) succeeds: RETURN true
14  RETURN false

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. Step 1: Start DFS at (row=0,col=0), flattened idx=0. Board[0][0]='A' matches word[0]='A'. Mark visited, look for 'B' (word[1]).
  2. Step 2: Move right to (row=0,col=1), idx=1. Board[0][1]='B' matches word[1]. Mark visited, look for 'C' (word[2]).
  3. Step 3: Move right to (row=0,col=2), idx=2. Board[0][2]='C' matches word[2]. Mark visited, look for next 'C' (word[3]).
  4. Step 4: Move down to (row=1,col=2), idx=5. Board[1][2]='C' matches word[3]. Mark visited, look for 'E' (word[4]).
  5. Step 5: Move down to (row=2,col=2), idx=8. Board[2][2]='E' matches word[4]. Mark visited, look for 'D' (word[5]).
  6. Step 6: Move left to (row=2,col=1), idx=7. Board[2][1]='D' matches word[5]. All 6 characters matched. Word "ABCCED" found via DFS path (0,0)→(0,1)→(0,2)→(1,2)→(2,2)→(2,1).
  7. Step 7: Backtrack completes. Un-mark all visited cells (visited[r][c] = False). Reset to search for other word instances or start positions. ans = true.
  8. Step 8: Alternative start — DFS from (row=1,col=1)=‘F’. This path does not lead to a match for "ABCCED" since 'F' ≠ 'A' (word[0]), so this start cell is skipped.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Word Search in the editorAll Matrix problemsBack to roadmap