Word Search in Grid Using Backtracking in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind backtracking in word search problems?

Backtracking tries to build a solution step-by-step, exploring all possible paths and undoing steps (backtracking) when a path does not lead to a solution.

beginner

In a word search grid, how do you decide the next cell to explore during backtracking?

You explore adjacent cells (up, down, left, right) that match the next character in the word and have not been visited yet.

beginner

Why do we mark cells as visited during backtracking in word search?

Marking cells as visited prevents revisiting the same cell in the current path, avoiding cycles and incorrect matches.

beginner

What is the base case for the recursive backtracking function in word search?

The base case is when all characters of the word have been matched successfully, meaning the word is found in the grid.

intermediate

How does backtracking ensure all possible paths are checked in the grid?

Backtracking explores one path fully, then backtracks to try other paths, ensuring every possible route is checked until the word is found or all options are exhausted.

Which directions are typically checked when searching for the next character in a word search grid?

A Up and Left only

B Up, Down, Left, Right

C Only Diagonal

D Random cells anywhere in the grid

The search moves to adjacent cells in four directions: up, down, left, and right.

What should you do if the current cell's character does not match the word's current character during backtracking?

A Backtrack and try a different path

B Continue exploring neighbors

C Mark the cell as visited anyway

D Stop the entire search

If the character does not match, backtrack to try other paths.

Why is it important to unmark a cell as visited when backtracking?

A It is not important

B To speed up the search

C To avoid infinite loops

D To allow revisiting it in other paths

Unmarking allows the cell to be used in different search paths.

What does the backtracking function return when the entire word is found?

A True

B False

C The length of the word

D The grid coordinates

It returns true to indicate the word has been found.

If the word is not found starting from a particular cell, what is the next step?

A Return true anyway

B Stop searching

C Try starting from the next cell in the grid

D Mark the word as found

You try starting from the next cell until all cells are checked.

Explain how backtracking works to find a word in a grid step-by-step.

Think about trying paths and undoing steps when stuck.

Describe why marking and unmarking visited cells is crucial in word search backtracking.

Consider what happens if you don't mark cells.

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)