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

Concept Flow - Word Search in Grid Using Backtracking

Start at each cell in grid

↓

Check if cell matches first letter of word

↓

If match, start backtracking

↓

Explore neighbors (up, down, left, right)

↓

Check if next letter matches and not visited

↓

If all letters matched

→Return True

↓

If no match or dead end

→Backtrack and try other paths

↓

If all cells tried and no match

→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 Rust

fn exist(board: &Vec<Vec<char>>, word: &str) -> bool {
    // Try each cell as start
    // Use backtracking to find word
    // Implementation omitted for brevity
}

This code tries to find if the word exists in the grid by exploring neighbors recursively.

Execution Table

Step	Operation	Current Position	Word Index	Visited Cells	Action	Visual State
1	Start at cell (0,0)	(0,0)	0	{}	Check if board[0][0] == word[0]	[W, E, L, C] [A, R, E, A] [T, T, I, N]
2	Match found	(0,0)	0	{(0,0)}	Move to neighbors for word[1]	[W, E, L, C] [A, R, E, A] [T, T, I, N]
3	Check neighbor (0,1)	(0,1)	1	{(0,0),(0,1)}	board[0][1] == 'E' matches word[1]	[W, E, L, C] [A, R, E, A] [T, T, I, N]
4	Check neighbor (0,2)	(0,2)	2	{(0,0),(0,1),(0,2)}	board[0][2] == 'L' matches word[2]	[W, E, L, C] [A, R, E, A] [T, T, I, N]
5	Check neighbor (0,3)	(0,3)	3	{(0,0),(0,1),(0,2),(0,3)}	board[0][3] == 'C' matches word[3]	[W, E, L, C] [A, R, E, A] [T, T, I, N]
6	Check neighbor (1,3)	(1,3)	4	{(0,0),(0,1),(0,2),(0,3),(1,3)}	board[1][3] == 'A' matches word[4]	[W, E, L, C] [A, R, E, A] [T, T, I, N]
7	Check neighbor (2,3)	(2,3)	5	{(0,0),(0,1),(0,2),(0,3),(1,3),(2,3)}	board[2][3] == 'N' matches word[5]	[W, E, L, C] [A, R, E, A] [T, T, I, N]
8	All letters matched	(2,3)	6	{(0,0),(0,1),(0,2),(0,3),(1,3),(2,3)}	Word found, return True	[W, E, L, C] [A, R, E, A] [T, T, I, N]
9	Exit	-	-	-	Stop search	[W, E, L, C] [A, R, E, A] [T, T, I, N]

💡 All letters matched at step 8, word found in grid

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	Final
Current Position	-	(0,0)	(0,2)	(1,3)	(2,3)	-
Word Index	0	1	3	5	6	-
Visited Cells	{}	{(0,0)}	{(0,0),(0,1),(0,2)}	{(0,0),(0,1),(0,2),(0,3),(1,3)}	{(0,0),(0,1),(0,2),(0,3),(1,3),(2,3)}	-

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 and incorrect matches. See steps 2-7 in execution_table where visited cells grow.

What happens if a neighbor cell does not match the next letter?

The algorithm backtracks by removing the cell from visited and tries other neighbors. This is implied between steps when no match is found and the search continues.

Why do we try every cell as a starting point?

Because the word can start anywhere in the grid, we must check all cells. Step 1 shows starting at (0,0), but if no match, other cells would be tried.

Visual Quiz - 3 Questions

Look at the execution_table, what is the set of visited cells after step 4?

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

B {(0,0),(0,1)}

C {(0,0),(0,1),(1,3)}

D {}

💡 Hint

Check the Visited Cells column at step 4 in execution_table

At which step does the algorithm confirm all letters of the word are matched?

A Step 6

B Step 8

C Step 5

D Step 9

💡 Hint

Look for 'All letters matched' in the Action column of execution_table

If the first cell (0,0) did not match the first letter, what would happen?

A The algorithm would stop immediately

B The algorithm would try the next cell as start

C The algorithm would return True anyway

D The algorithm would skip backtracking

💡 Hint

Refer to concept_flow where each cell is tried as a start

Concept Snapshot

Word Search uses backtracking to find a word in a grid.
Start from each cell, check if it matches the first letter.
If yes, recursively explore neighbors for next letters.
Mark visited cells to avoid reuse in the same path.
Backtrack if a path fails, try other paths.
Return true if all letters matched, else false.

Full Transcript

This visualization shows how the word search algorithm works using backtracking. It starts at each cell in the grid, checking if the cell matches the first letter of the word. If it matches, it marks the cell as visited and explores neighboring cells (up, down, left, right) to find the next letter. The algorithm continues this process, marking visited cells to avoid revisiting them in the same path. If a neighbor does not match or leads to a dead end, it backtracks by unmarking the cell and tries other neighbors. This continues until all letters are matched, returning true, or all possibilities are exhausted, returning false. The execution table traces the steps, showing positions, visited cells, and actions. Key moments clarify why visited marking is important, how backtracking works, and why every cell is tried as a start. The quiz tests understanding of visited sets, matching completion, and starting points.

Practice

1. What are the four directions checked at each cell during word search backtracking?

easy

A. Up, Down, Left, Right (4-directional)

B. All 8 directions including diagonals

C. Only Right and Down

D. Only the direction the path came from

Solution

1. Step 1: Standard word search

   Uses 4-directional movement: up(-1,0), down(+1,0), left(0,-1), right(0,+1).

2. Final Answer:

   4-directional: up, down, left, right. -> Option A

3. Quick Check:

   Standard = 4 dirs. 8-directional is a variant. [OK]

Hint: Word search = 4 directions (UDLR). 8-directional with diagonals is a variant. [OK]

Common Mistakes:

• Using 8 directions when problem specifies 4
• Only checking right and down
• Not using i32 offsets in Rust for signed arithmetic

2. In word search using backtracking, why must we mark a cell as visited before recursing into its neighbors?

medium

A. To avoid counting the same cell in the word length

B. To prevent reusing the same cell in a single word path

C. To speed up the search by skipping visited cells globally

D. Because Rust borrow checker requires it

Solution

1. Step 1: Word path constraint

   Each cell can be used at most once in a single word path. Without marking, a path could revisit the same cell.

2. Step 2: Visited marking

   Mark cell before recursing (visited=true). After returning, unmark (backtrack). This ensures no cell is reused in the current path.

3. Final Answer:

   Prevent reusing the same cell within one word path. -> Option B

4. Quick Check:

   Mark before recurse, unmark on backtrack. [OK]

Hint: Mark visited before recurse, unmark on backtrack. Prevents same cell reuse in one path. [OK]

Common Mistakes:

• Thinking visited is global (it is path-local)
• Not unmarking after backtrack
• Confusing with BFS visited which is permanent

3. What is the pruning condition that immediately returns false in word search backtracking?

medium

A. When the current cell value > word[index]

B. When row or col is out of bounds, cell is visited, or grid[r][c] != word[index]

C. When index > word.len() / 2

D. When we have already found one valid path

Solution

1. Step 1: Three pruning conditions

   (1) Out of bounds. (2) Already visited. (3) Character mismatch: grid[r][c] != word[index].

2. Final Answer:

   Out of bounds OR visited OR character mismatch. -> Option B

3. Quick Check:

   Prune when: out-of-grid || visited || wrong char. Any one = false. [OK]

Hint: Prune: out-of-bounds || visited || grid[r][c]!=word[i]. Any one triggers false. [OK]

Common Mistakes:

• Only checking bounds but not character match
• Not checking visited
• Pruning at index threshold instead of character match

4. What is the base case (success condition) in word search backtracking?

medium

A. When row == grid.len()

B. When index == word.len() - all characters matched

C. When we reach the grid boundary

D. When all cells are visited

Solution

1. Step 1: What index tracks

   index tracks characters matched. When index == word.len(), all matched.

2. Final Answer:

   index == word.len() - entire word matched. -> Option B

3. Quick Check:

   Base case: index == word.len() = found, return true. [OK]

Hint: Success: index == word.len(). Checked first before bounds/char checks. [OK]

Common Mistakes:

• Checking index == word.len()-1 (off by one)
• Checking grid boundary instead of word index
• Not returning immediately on success

5. What is the worst-case time complexity of word search backtracking on an m x n grid with word length L?

hard

A. O(m x n x L)

B. O(m x n x 4^L)

C. O((m x n)^2)

D. O(m x n x L^2)

Solution

1. Step 1: Starting positions

   O(m x n) starting cells.

2. Step 2: Branching

   At each of L steps, up to 4 directions: 4^L paths per start.

3. Final Answer:

   O(m x n x 4^L) -> Option B

4. Quick Check:

   m x n starts x 4^L paths = O(m x n x 4^L). [OK]

Hint: Word search worst case: O(m x n x 4^L). Exponential in word length. [OK]

Common Mistakes:

• Saying O(m x n x L) ignoring branching factor
• Not knowing 4^L from 4 dirs x L steps
• Confusing with BFS which is O(m x n)