Word Search in Grid Using Backtracking in DSA Rust

Mental Model

We try to find a word by moving step-by-step in the grid, checking each letter and going back if it doesn't fit.

Analogy: Imagine walking through a maze where each step must match a letter in the word; if you hit a dead end, you retrace your steps and try a different path.

Grid:
A B C E
S F C S
A D E E

Word: SEE

Positions marked with ↑ show current search position.

Dry Run Walkthrough

Input: Grid: [['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], Word: 'SEE'

Goal: Find if the word 'SEE' exists by moving horizontally or vertically in the grid.

Step 1: Start at cell (0,0) with letter 'A', does not match 'S', move to next cell

Grid unchanged, current position at (0,1) 'B'

Why: We look for the first letter 'S' to start matching

Step 2: At cell (1,0) letter 'S', matches first letter of word, start backtracking

Mark (1,0) as visited, current matched letters: 'S'

Why: Found starting point for the word

Step 3: Check neighbors of (1,0): (0,0), (2,0), (1,-1), (1,1). (2,0) is 'A' no match, (1,1) is 'F' no match, (0,0) is 'A' no match

Only (1,1) and (2,0) checked, no match for second letter 'E'

Why: Try to find next letter 'E' adjacent to current position

Step 4: Backtrack from (1,0), unmark visited, move to cell (1,3) 'S' which matches first letter

Mark (1,3) as visited, matched 'S'

Why: Try another starting point for the word

Step 5: Check neighbors of (1,3): (0,3) 'E', matches second letter 'E', move there

Mark (0,3) visited, matched 'SE'

Why: Found next letter in the word

Step 6: Check neighbors of (0,3): (0,2) 'C', (1,3) visited, (-1,3) invalid, (0,4) invalid. No match for third letter 'E' here

No valid moves, backtrack to (1,3)

Why: Dead end, need to try other neighbors

Step 7: Check other neighbors of (1,3): (2,3) 'E', matches third letter 'E', move there

Mark (2,3) visited, matched 'SEE'

Why: Found complete word

Result:

Path found: (1,3) 'S' -> (0,3) 'E' -> (2,3) 'E'
Word 'SEE' exists in the grid

Annotated Code

DSA Rust

use std::collections::HashSet;

struct Solution;

impl Solution {
    fn exist(board: Vec<Vec<char>>, word: String) -> bool {
        let rows = board.len();
        if rows == 0 { return false; }
        let cols = board[0].len();
        if cols == 0 { return false; }
        let word_chars: Vec<char> = word.chars().collect();

        fn backtrack(
            board: &Vec<Vec<char>>,
            word: &Vec<char>,
            index: usize,
            row: usize,
            col: usize,
            visited: &mut HashSet<(usize, usize)>,
        ) -> bool {
            if index == word.len() {
                return true; // All letters matched
            }
            if row >= board.len() || col >= board[0].len() {
                return false; // Out of bounds
            }
            if board[row][col] != word[index] {
                return false; // Letter does not match
            }
            if visited.contains(&(row, col)) {
                return false; // Already visited this cell
            }

            visited.insert((row, col));

            // Explore neighbors: up, down, left, right
            let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)];
            for (dr, dc) in directions.iter() {
                let new_row = row as isize + dr;
                let new_col = col as isize + dc;
                if new_row >= 0
                    && new_row < board.len() as isize
                    && new_col >= 0
                    && new_col < board[0].len() as isize
                {
                    if backtrack(
                        board,
                        word,
                        index + 1,
                        new_row as usize,
                        new_col as usize,
                        visited,
                    ) {
                        return true; // Found path
                    }
                }
            }

            visited.remove(&(row, col)); // Backtrack
            false
        }

        for r in 0..rows {
            for c in 0..cols {
                let mut visited = HashSet::new();
                if backtrack(&board, &word_chars, 0, r, c, &mut visited) {
                    return true;
                }
            }
        }
        false
    }
}

fn main() {
    let board = vec![
        vec!['A', 'B', 'C', 'E'],
        vec!['S', 'F', 'C', 'S'],
        vec!['A', 'D', 'E', 'E'],
    ];
    let word = String::from("SEE");
    let result = Solution::exist(board, word);
    println!("{}", result);
}

if index == word.len() { return true; }

All letters matched, successful end condition

if row >= board.len() || col >= board[0].len() { return false; }

Check out of bounds to avoid invalid access

if board[row][col] != word[index] { return false; }

Current cell letter must match current word letter

if visited.contains(&(row, col)) { return false; }

Avoid revisiting same cell in current path

visited.insert((row, col));

Mark current cell as visited before exploring neighbors

for (dr, dc) in directions.iter() { ... backtrack(...) }

Explore all four directions recursively for next letter

visited.remove(&(row, col));

Backtrack by unmarking cell if path fails

for r in 0..rows { for c in 0..cols { ... backtrack(...) } }

Try starting backtracking from every cell in the grid

Output

true

Complexity Analysis

Time: O(N * 3^L) where N is number of cells and L is word length because each cell can start a search and each step explores up to 3 directions (excluding the one we came from).

Space: O(L) for recursion stack and visited set because the maximum depth is the length of the word.

vs Alternative: Naive approach checks all paths without pruning visited cells, leading to exponential blowup; backtracking with visited pruning reduces unnecessary paths.

Edge Cases

Empty grid

Returns false immediately as no letters to match

DSA Rust

if rows == 0 || cols == 0 { return false; }

Word longer than total cells

Returns false since word cannot fit

DSA Rust

if index == word.len() { return true; }

Word with repeated letters requiring revisiting cells

Does not revisit cells in same path, avoids false positives

DSA Rust

if visited.contains(&(row, col)) { return false; }

When to Use This Pattern

When asked to find a word or pattern in a grid by moving stepwise with constraints, use backtracking to explore all possible paths while avoiding revisits.

Common Mistakes

Mistake: Not marking cells as visited causing infinite loops or revisiting same cell multiple times
Fix: Use a visited set or mark cells before recursive calls and unmark after to backtrack

Mistake: Not checking boundary conditions leading to index out of bounds errors
Fix: Always check row and column indices before accessing grid cells

Summary

Finds if a word exists in a grid by moving horizontally or vertically using backtracking.

Use when searching for sequences in grids with movement constraints and need to explore multiple paths.

The key is to try each path step-by-step and backtrack when a path does not lead to a solution.

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)