Word Search in Grid Using Backtracking in DSA Java - Execution Trace

Concept Flow - Word Search in Grid Using Backtracking

Start at each cell in grid

↓

Check if cell matches first letter of word

Yes↓

Mark cell as visited

↓

Explore neighbors (up, down, left, right)

↓

For each neighbor: matches next letter?

↓

Backtrack

↓

Recursive call on neighbor

↓

If full word matched

↓

Return true

↓

Backtrack: unmark cell

↓

Try next neighbor or next start cell

↓

If no match found, return false

The algorithm tries each cell as a start, then uses backtracking to explore neighbors matching the word letters step-by-step.

Execution Sample

DSA Java

boolean exist(char[][] board, String word) {
  for (int i = 0; i < board.length; i++) {
    for (int j = 0; j < board[0].length; j++) {
      if (backtrack(board, word, i, j, 0)) return true;
    }
  }
  return false;
}

Check each cell in the grid to find the word using backtracking.

Execution Table

Step	Operation	Current Cell (row,col)	Word Index	Visited Cells	Action	Visual State
1	Start at cell	(0,0)	0	{}	Check if board[0][0] == word[0]	[W][O][R] [A][B][C] [D][E][F]
2	Match first letter	(0,0)	0	{}	board[0][0] == 'W' matches word[0] 'W'	[W][O][R] [A][B][C] [D][E][F]
3	Mark visited	(0,0)	0	{(0,0)}	Mark (0,0) visited	[*W*][O][R] [A][B][C] [D][E][F]
4	Explore neighbors	(0,1)	1	{(0,0)}	Check board[0][1] == word[1] 'O'	[*W*][O][R] [A][B][C] [D][E][F]
5	Match letter	(0,1)	1	{(0,0)}	board[0][1] == 'O' matches word[1]	[*W*][*O*][R] [A][B][C] [D][E][F]
6	Mark visited	(0,1)	1	{(0,0),(0,1)}	Mark (0,1) visited	[*W*][*O*][R] [A][B][C] [D][E][F]
7	Explore neighbors	(0,2)	2	{(0,0),(0,1)}	Check board[0][2] == word[2] 'R'	[*W*][*O*][R] [A][B][C] [D][E][F]
8	Match letter	(0,2)	2	{(0,0),(0,1)}	board[0][2] == 'R' matches word[2]	[*W*][*O*][*R*] [A][B][C] [D][E][F]
9	Mark visited	(0,2)	2	{(0,0),(0,1),(0,2)}	Mark (0,2) visited	[*W*][*O*][*R*] [A][B][C] [D][E][F]
10	Explore neighbors	(1,2)	3	{(0,0),(0,1),(0,2)}	Check board[1][2] == word[3] 'D'	[*W*][*O*][*R*] [A][B][C] [D][E][F]
11	No match	(1,2)	3	{(0,0),(0,1),(0,2)}	board[1][2] == 'C' != 'D', backtrack	[*W*][*O*][*R*] [A][B][C] [D][E][F]
12	Backtrack	(0,2)	2	{(0,0),(0,1)}	Unmark (0,2)	[*W*][*O*][R] [A][B][C] [D][E][F]
13	Explore neighbors	(1,1)	2	{(0,0),(0,1)}	Check board[1][1] == word[2] 'R'	[*W*][*O*][R] [A][B][C] [D][E][F]
14	No match	(1,1)	2	{(0,0),(0,1)}	board[1][1] == 'B' != 'R', backtrack	[*W*][*O*][R] [A][B][C] [D][E][F]
15	Backtrack	(0,1)	1	{(0,0)}	Unmark (0,1)	[*W*][O][R] [A][B][C] [D][E][F]
16	Explore neighbors	(1,0)	1	{(0,0)}	Check board[1][0] == word[1] 'O'	[*W*][O][R] [A][B][C] [D][E][F]
17	No match	(1,0)	1	{(0,0)}	board[1][0] == 'A' != 'O', backtrack	[*W*][O][R] [A][B][C] [D][E][F]
18	Backtrack	(0,0)	0	{}	Unmark (0,0)	[W][O][R] [A][B][C] [D][E][F]
19	Start at cell	(0,1)	0	{}	Check if board[0][1] == word[0] 'W'	[W][O][R] [A][B][C] [D][E][F]
20	No match	(0,1)	0	{}	board[0][1] == 'O' != 'W', move to next cell	[W][O][R] [A][B][C] [D][E][F]
...	...	...	...	...	...	...
N	No match found in any cell	N/A	N/A	{}	Return false	[W][O][R] [A][B][C] [D][E][F]

💡 All cells checked, no full word match found, return false

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 12	After Step 15	After Step 18	Final
Visited Cells	{}	{(0,0)}	{(0,0),(0,1)}	{(0,0),(0,1),(0,2)}	{(0,0),(0,1)}	{(0,0)}	{}	{}
Current Cell	N/A	(0,0)	(0,1)	(0,2)	(0,2)	(0,1)	(0,0)	N/A
Word Index	0	0	1	2	2	1	0	N/A

Key Moments - 3 Insights

Why do we mark cells as visited during backtracking?

Marking cells as visited prevents revisiting the same cell in the current path, avoiding infinite loops. See steps 3, 6, and 9 where cells are marked, and steps 12 and 15 where they are unmarked.

Why do we backtrack (unmark) cells after exploring neighbors?

Backtracking unmarks cells so they can be used in other paths starting from different cells. This is shown in steps 12 and 15 where visited cells are unmarked after no match is found.

Why do we check neighbors only in four directions (up, down, left, right)?

The problem defines neighbors as adjacent horizontally or vertically, not diagonally. This limits exploration to four directions as shown in the exploration steps.

Visual Quiz - 3 Questions

Look at the execution table at step 6, which cells are marked visited?

A {(0,0),(0,1)}

B {(0,0)}

C {(0,1)}

D {}

💡 Hint

Check the 'Visited Cells' column at step 6 in the execution_table.

At which step does the algorithm backtrack from cell (0,2)?

A Step 9

B Step 12

C Step 15

D Step 18

💡 Hint

Look for 'Backtrack' operation involving (0,2) in the execution_table.

If the word started with letter 'A' instead of 'W', what would happen at step 2?

A The check would pass and start backtracking from (0,0)

B The check would fail and move to next cell

C The algorithm would immediately return true

D The algorithm would skip the first row

💡 Hint

Step 2 shows the first letter match check; changing the word's first letter affects this step.

Concept Snapshot

Word Search Backtracking:
- Start from each cell
- Check if cell matches current word letter
- Mark cell visited
- Recursively explore neighbors (up, down, left, right)
- Backtrack by unmarking if path fails
- Return true if full word matched, else false

Full Transcript

This visualization shows how the word search algorithm uses backtracking to find a word in a grid. It starts at each cell, checks if the letter matches the first letter of the word, then marks the cell visited. It explores neighbors recursively to match the next letters. If a path fails, it backtracks by unmarking cells to try other paths. The execution table tracks each step, the current cell, visited cells, and the visual state of the grid. Key moments explain why marking visited cells and backtracking are necessary. The quiz tests understanding of visited cells, backtracking steps, and letter matching.

Practice

1. What is the main purpose of backtracking in the Word Search problem on a grid?

easy

A. To sort the grid alphabetically

B. To explore all possible paths to find the word

C. To count the number of words in the grid

D. To replace characters in the grid

Solution

1. Step 1: Understand backtracking role

   Backtracking tries all possible paths in the grid to find the target word by moving in allowed directions.

2. Step 2: Eliminate other options

   Sorting, counting, or replacing characters are unrelated to searching paths for the word.

3. Final Answer:

   To explore all possible paths to find the word -> Option B

4. Quick Check:

   Backtracking = Explore paths [OK]

Hint: Backtracking means trying all paths until word found [OK]

Common Mistakes:

• Thinking backtracking sorts or modifies the grid
• Confusing backtracking with simple search
• Assuming backtracking counts words instead of searching

2. Which of the following Java method signatures correctly represents a backtracking helper for word search in a grid?

easy

A. boolean backtrack(char[][] board, String word, int index, int row, int col)

B. void backtrack(char[] board, String word, int index)

C. int backtrack(char[][] board, String word, int row, int col)

D. String backtrack(char[][] board, String word, int index, int row, int col)

Solution

1. Step 1: Check method parameters

   The method needs the board (2D char array), the word, current index in word, and current position (row, col) to explore.

2. Step 2: Check return type

   Backtracking returns boolean to indicate if word is found along this path.

3. Final Answer:

   boolean backtrack(char[][] board, String word, int index, int row, int col) -> Option A

4. Quick Check:

   Correct signature = boolean backtrack(char[][] board, String word, int index, int row, int col) [OK]

Hint: Backtracking returns boolean and needs position + index [OK]

Common Mistakes:

• Using 1D array instead of 2D for board
• Wrong return type like int or String
• Missing index or position parameters

3. Given the grid:

[['A','B','C','E'],
 ['S','F','C','S'],
 ['A','D','E','E']]

and the word "ABCCED", what will the backtracking function return?

medium

A. throws Exception

B. false

C. null

D. true

Solution

1. Step 1: Trace the word in the grid

   The word "ABCCED" can be found by path: A(0,0) -> B(0,1) -> C(0,2) -> C(1,2) -> E(2,2) -> D(2,1).

2. Step 2: Backtracking confirms path exists

   Since the path exists without revisiting cells, backtracking returns true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Word found = true [OK]

Hint: Trace path step-by-step to confirm word presence [OK]

Common Mistakes:

• Assuming word is not found without checking all directions
• Confusing similar letters in different positions
• Ignoring backtracking's ability to explore multiple paths

4. Consider this backtracking snippet for word search:

if (row < 0 || col < 0 || row >= board.length || col >= board[0].length || board[row][col] != word.charAt(index)) {
    return false;
}

What is the main issue if we forget to mark visited cells during recursion?

medium

A. The function may revisit the same cell causing infinite loops

B. The function will always return true

C. The function will throw an ArrayIndexOutOfBoundsException

D. The function will skip valid paths

Solution

1. Step 1: Understand visited marking role

   Marking visited cells prevents revisiting the same cell in the current path, avoiding cycles.

2. Step 2: Consequence of missing visited marking

   Without marking, recursion may revisit cells endlessly, causing infinite loops or stack overflow.

3. Final Answer:

   The function may revisit the same cell causing infinite loops -> Option A

4. Quick Check:

   Missing visited mark = infinite loops [OK]

Hint: Always mark visited cells to avoid loops [OK]

Common Mistakes:

• Assuming no visited marking is safe
• Confusing out-of-bound checks with visited logic
• Thinking missing visited causes exceptions instead of loops

5. You want to find if the word "SEE" exists in the grid:

[['A','B','C','E'],
 ['S','F','E','S'],
 ['A','D','E','E']]

Using backtracking, which approach correctly handles multiple possible paths and avoids revisiting cells?

hard

A. Only search in one direction (right) to reduce complexity

B. Modify the board characters to '*' when visited and never revert them

C. Use a boolean visited[][] array to mark cells during recursion and backtrack by unmarking after recursion returns

D. Use a global counter to limit recursion depth

Solution

1. Step 1: Understand visited marking with backtracking

   Using a boolean visited array allows marking cells as visited during recursion and unmarking them after exploring all paths from that cell.

2. Step 2: Evaluate other options

   Modifying board permanently breaks original data, searching only right misses paths, and limiting recursion depth does not solve revisiting.

3. Final Answer:

   Use a boolean visited[][] array to mark cells during recursion and backtrack by unmarking after recursion returns -> Option C

4. Quick Check:

   Visited array + backtrack unmark = correct approach [OK]

Hint: Mark visited with boolean array and unmark after recursion [OK]

Common Mistakes:

• Permanently changing board characters
• Ignoring directions other than right
• Using recursion limits instead of visited marking