Word Search in Grid Using Backtracking in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Word Search Result in Grid

What is the output of the Rust program that checks if the word "CAT" exists in the given 3x3 grid using backtracking?

DSA Rust

fn exist(board: &Vec<Vec<char>>, word: &str) -> bool {
    fn backtrack(board: &Vec<Vec<char>>, word: &[char], i: usize, x: usize, y: usize, visited: &mut Vec<Vec<bool>>) -> bool {
        if i == word.len() {
            return true;
        }
        if x >= board.len() || y >= board[0].len() || board[x][y] != word[i] || visited[x][y] {
            return false;
        }
        visited[x][y] = true;
        let directions = [(1,0), (-1,0), (0,1), (0,-1)];
        for &(dx, dy) in &directions {
            let nx = x as isize + dx;
            let ny = y as isize + dy;
            if nx >= 0 && ny >= 0 && (nx as usize) < board.len() && (ny as usize) < board[0].len() && backtrack(board, word, i+1, nx as usize, ny as usize, visited) {
                return true;
            }
        }
        visited[x][y] = false;
        false
    }
    let word_chars: Vec<char> = word.chars().collect();
    let mut visited = vec![vec![false; board[0].len()]; board.len()];
    for i in 0..board.len() {
        for j in 0..board[0].len() {
            if backtrack(board, &word_chars, 0, i, j, &mut visited) {
                return true;
            }
        }
    }
    false
}

fn main() {
    let board = vec![
        vec!['C', 'A', 'T'],
        vec!['X', 'Y', 'Z'],
        vec!['A', 'B', 'C'],
    ];
    let word = "CAT";
    println!("{}", exist(&board, word));
}

A true

B false

C Compilation error

D Runtime panic

💡 Hint

Think about whether the word "CAT" can be found by moving horizontally or vertically in the grid.

The word "CAT" can be found in the first row of the grid moving from left to right. The backtracking function returns true when it finds the complete word.

🧠 Conceptual

intermediate

Understanding Backtracking Directions

In the backtracking approach for word search in a grid, which directions are typically checked to find the next character?

A Diagonals only

B Up, Down, Left, Right

C Up and Left only

D All eight directions including diagonals

💡 Hint

Consider the problem constraints that usually allow moving only horizontally or vertically.

The standard word search problem allows moving only up, down, left, or right to find the next character.

🔧 Debug

advanced

Identify the Bug in Backtracking Visited Reset

What is the bug in this backtracking snippet for word search that causes incorrect results? ```rust visited[x][y] = true; for &(dx, dy) in &directions { let nx = x as isize + dx; let ny = y as isize + dy; if nx >= 0 && ny >= 0 && backtrack(board, word, i+1, nx as usize, ny as usize, visited) { return true; } } // Missing visited[x][y] = false here false ```

A The function does not check if x or y are out of bounds before accessing board.

B The directions array is missing diagonal moves.

C The base case for i == word.len() is missing.

D The visited[x][y] is not reset to false after recursion, causing false negatives.

💡 Hint

Think about what happens if you don't mark a cell as unvisited after exploring it.

Not resetting visited[x][y] to false after exploring causes the algorithm to think the cell is permanently visited, blocking valid paths.

❓ Predict Output

advanced

Output of Word Search for Non-Existent Word

What is the output of the Rust program when searching for the word "DOG" in the following grid? [['C', 'A', 'T'], ['X', 'Y', 'Z'], ['A', 'B', 'C']]

DSA Rust

fn main() {
    let board = vec![
        vec!['C', 'A', 'T'],
        vec!['X', 'Y', 'Z'],
        vec!['A', 'B', 'C'],
    ];
    let word = "DOG";
    println!("{}", exist(&board, word));
}

fn exist(board: &Vec<Vec<char>>, word: &str) -> bool {
    fn backtrack(board: &Vec<Vec<char>>, word: &[char], i: usize, x: usize, y: usize, visited: &mut Vec<Vec<bool>>) -> bool {
        if i == word.len() {
            return true;
        }
        if x >= board.len() || y >= board[0].len() || board[x][y] != word[i] || visited[x][y] {
            return false;
        }
        visited[x][y] = true;
        let directions = [(1,0), (-1,0), (0,1), (0,-1)];
        for &(dx, dy) in &directions {
            let nx = x as isize + dx;
            let ny = y as isize + dy;
            if nx >= 0 && ny >= 0 && (nx as usize) < board.len() && (ny as usize) < board[0].len() && backtrack(board, word, i+1, nx as usize, ny as usize, visited) {
                return true;
            }
        }
        visited[x][y] = false;
        false
    }
    let word_chars: Vec<char> = word.chars().collect();
    let mut visited = vec![vec![false; board[0].len()]; board.len()];
    for i in 0..board.len() {
        for j in 0..board[0].len() {
            if backtrack(board, &word_chars, 0, i, j, &mut visited) {
                return true;
            }
        }
    }
    false
}

A Compilation error

B true

C false

D Runtime panic

💡 Hint

Check if the letters D, O, G appear in sequence in the grid.

The word "DOG" does not appear in the grid in any path moving up, down, left, or right.

🚀 Application

expert

Minimum Steps to Form Word in Grid

Given a grid and a word, what is the minimum number of steps required to form the word by moving horizontally or vertically from one letter to the next? Assume you can start at any cell containing the first letter. Which approach best solves this problem?

A Use backtracking with pruning to explore all paths and track minimum steps.

B Use a simple linear scan of the grid without recursion.

C Use a stack-based depth-first search without tracking visited cells.

D Use sorting of grid letters and binary search to find the word.

💡 Hint

Think about exploring all possible paths but stopping early when paths are longer than current minimum.

Backtracking with pruning allows exploring all valid paths while avoiding unnecessary work, enabling finding the minimum steps.

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)