Word Search in Grid Using Backtracking in DSA Rust - Time & Space Complexity

Time Complexity: Word Search in Grid Using Backtracking

O(m * n * 4^k)

Understanding Time Complexity

We want to understand how the time needed to find a word in a grid grows as the grid or word size changes.

Specifically, how does the search time increase when the grid or word gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn exist(board: &Vec>, word: &str) -> bool {
    fn backtrack(board: &Vec>, word: &[char], i: usize, x: usize, y: usize, visited: &mut Vec>) -> bool {
        if i == word.len() { return true; }
        if x >= board.len() || y >= board[0].len() || visited[x][y] || board[x][y] != word[i] { 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 = 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
}
    

This code tries to find if a word exists in a 2D grid by checking each cell and exploring neighbors recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive backtracking exploring up to 4 directions from each cell.
• How many times: For each cell in the grid (m rows * n columns), it may explore up to 4 neighbors for each character in the word (length k).

How Execution Grows With Input

As the grid size (m*n) or word length (k) grows, the search explores many paths.

Input Size (m*n, k)	Approx. Operations
10x10 grid, word length 3	About 10*10 * 4^3 = 6400 checks
10x10 grid, word length 5	About 10*10 * 4^5 = 102,400 checks
20x20 grid, word length 5	About 20*20 * 4^5 = 409,600 checks

Pattern observation: The operations grow quickly because each character can lead to 4 new paths, causing exponential growth with word length.

Final Time Complexity

Time Complexity: O(m * n * 4^k)

This means the time grows quickly with the word length, as each letter can branch into 4 directions, and we try starting from every cell.

Common Mistake

[X] Wrong: "The search only checks each cell once, so it is just O(m*n)."

[OK] Correct: Because the search explores many paths recursively for each character, it can revisit cells in different paths, causing exponential growth with word length.

Interview Connect

Understanding this complexity helps you explain how backtracking explores many possibilities and why pruning or early stopping matters.

Self-Check

"What if we limited the search to only horizontal and vertical neighbors, removing diagonal moves? How would the time complexity change?"

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)