Word Search in Grid Using Backtracking in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the current cell matches the current character of the word.

DSA Rust

if board[row][col] == word.chars().nth([1]).unwrap() {

Drag options to blanks, or click blank then click option'

Apos

Bi

Cindex

Dcount

Attempts:

3 left

💡 Hint

Common Mistakes

Using a variable that is not defined or not the index for the word characters.

The variable 'i' is commonly used as the index for the current character in the word during backtracking.

2fill in blank

medium

Complete the code to mark the current cell as visited by replacing its character.

DSA Rust

let temp = board[row][col];
board[row][col] = [1];

Drag options to blanks, or click blank then click option'

A'#'

B' '

C'*'

D'$'

Attempts:

3 left

💡 Hint

Common Mistakes

Using a character that might appear in the board and cause incorrect matches.

Using '#' is a common way to mark a cell as visited temporarily in backtracking.

3fill in blank

hard

Fix the error in the recursive call to explore neighbors in four directions.

DSA Rust

let found = dfs(board, word, row + [1], col, i + 1) || dfs(board, word, row, col + [2], i + 1) || dfs(board, word, row - [3], col, i + 1) || dfs(board, word, row, col - 1, i + 1);

Drag options to blanks, or click blank then click option'

A1

B-1

C0

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong increments or decrements for row and col in recursive calls.

To move down, add 1 to row; to move right, add 1 to col; to move up, subtract 1 from row; to move left, subtract 1 from col.

4fill in blank

hard

Fill both blanks to restore the original character after backtracking and return the result.

DSA Rust

board[row][col] = [1];
return [2];

Drag options to blanks, or click blank then click option'

Atemp

Bfound

Ctrue

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Not restoring the cell, causing incorrect future matches.

Returning a wrong boolean value.

We restore the cell to its original character stored in 'temp' and return whether the word was found in 'found'.

5fill in blank

hard

Fill all three blanks to complete the main function that starts the search for the word in the grid.

DSA Rust

for row in 0..[1] {
    for col in 0..[2] {
        if dfs(&mut board, &word, row, col, 0) == [3] {
            return true;
        }
    }
}
return false;

Drag options to blanks, or click blank then click option'

Aboard.len()

Bboard[0].len()

Ctrue

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong loop bounds causing index errors.

Returning false instead of true when word is found.

We loop over all rows and columns using board dimensions and return true if dfs finds the word.

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)