Word Search in Grid Using Backtracking in DSA Rust - Build from Scratch

Word Search in Grid Using Backtracking

📖 Scenario: You are building a simple word search puzzle solver. The puzzle is a grid of letters, and you want to find if a given word exists in the grid by moving horizontally or vertically to adjacent letters.This is like searching for a hidden word in a crossword puzzle.

🎯 Goal: Build a program that checks if a given word can be found in the letter grid by moving up, down, left, or right without revisiting the same cell.

📋 What You'll Learn

Create a 2D vector of characters representing the letter grid.

Create a string variable for the word to search.

Implement a backtracking function to search the word in the grid.

Print true if the word is found, otherwise false.

💡 Why This Matters

🌍 Real World

Word search puzzles are common in newspapers and apps. This technique helps solve or generate such puzzles automatically.

💼 Career

Backtracking algorithms are used in many fields like game development, AI, and solving constraint problems. Understanding this helps in coding interviews and real-world problem solving.

1

Create the letter grid

Create a 2D vector of characters called board with these exact rows:
['A', 'B', 'C', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E']

DSA Rust

# Create the 2D vector called board with the given rows
# Your code here

Hint

Use vec![vec!['A', 'B', 'C', 'E'], ...] to create the 2D vector.

2

Create the word to search

Add a string variable called word and set it to "ABCCED"

DSA Rust

fn main() {
    let board = vec![
        vec!['A', 'B', 'C', 'E'],
        vec!['S', 'F', 'C', 'S'],
        vec!['A', 'D', 'E', 'E'],
    ];
    // Create the word variable here
    # Your code here
}

Hint

Use String::from("ABCCED") to create the word string.

3

Implement the backtracking search function

Add a function called exist that takes board: &Vec> and word: &str and returns bool. Implement backtracking inside exist to check if word exists in board. Use helper function dfs with parameters board, word, index, row, col, and a mutable 2D vector visited to track visited cells. The search moves up, down, left, and right. Return true if the word is found, otherwise false. Call exist(&board, &word) inside main and store the result in a variable found.

DSA Rust

fn main() {
    let board = vec![
        vec!['A', 'B', 'C', 'E'],
        vec!['S', 'F', 'C', 'S'],
        vec!['A', 'D', 'E', 'E'],
    ];
    let word = String::from("ABCCED");
    // Call exist function and store result in found
    # Your code here
}

// Define exist function and dfs helper below
// Your code here

Hint

Use a helper function dfs to explore neighbors recursively. Mark cells visited to avoid reuse.

4

Print the search result

Add a println! statement in main to print the value of found which shows if the word was found in the grid.

DSA Rust

fn main() {
    let board = vec![
        vec!['A', 'B', 'C', 'E'],
        vec!['S', 'F', 'C', 'S'],
        vec!['A', 'D', 'E', 'E'],
    ];
    let word = String::from("ABCCED");
    let found = exist(&board, &word);
    // Print the value of found
    # Your code here
}

// exist and dfs functions below
// (already implemented)

Hint

Use println!("{}", found); to print the boolean result.

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)