Word Search in Grid Using Backtracking in DSA C

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: Like exploring a maze where you try a path, and if it leads nowhere, you return and try another path until you find the exit.

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

Start at any cell matching first letter, move up/down/left/right to next letter.

Dry Run Walkthrough

Input: Grid: [['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], word: "ABCCED"

Goal: Find if the word "ABCCED" exists by moving horizontally or vertically in the grid.

Step 1: Start at cell (0,0) with letter 'A' matching first letter

A[0,0] -> B[0,1] -> C[0,2] -> E[0,3]
S[1,0] -> F[1,1] -> C[1,2] -> S[1,3]
A[2,0] -> D[2,1] -> E[2,2] -> E[2,3]
↑ at (0,0)

Why: We must find the first letter to start the search

Step 2: Move right to (0,1) with letter 'B' matching second letter

A[0,0] -> B[0,1] -> C[0,2] -> E[0,3]
S[1,0] -> F[1,1] -> C[1,2] -> S[1,3]
A[2,0] -> D[2,1] -> E[2,2] -> E[2,3]
↑ at (0,1)

Why: Next letter must be adjacent horizontally or vertically

Step 3: Move right to (0,2) with letter 'C' matching third letter

A[0,0] -> B[0,1] -> C[0,2] -> E[0,3]
S[1,0] -> F[1,1] -> C[1,2] -> S[1,3]
A[2,0] -> D[2,1] -> E[2,2] -> E[2,3]
↑ at (0,2)

Why: Continue matching letters in sequence

Step 4: Move down to (1,2) with letter 'C' matching fourth letter

A[0,0] -> B[0,1] -> C[0,2] -> E[0,3]
S[1,0] -> F[1,1] -> C[1,2] -> S[1,3]
A[2,0] -> D[2,1] -> E[2,2] -> E[2,3]
↑ at (1,2)

Why: Letters can be adjacent vertically

Step 5: Move down to (2,2) with letter 'E' matching fifth letter

A[0,0] -> B[0,1] -> C[0,2] -> E[0,3]
S[1,0] -> F[1,1] -> C[1,2] -> S[1,3]
A[2,0] -> D[2,1] -> E[2,2] -> E[2,3]
↑ at (2,2)

Why: Continue following the word path

Step 6: Move left to (2,1) with letter 'D' matching sixth letter

A[0,0] -> B[0,1] -> C[0,2] -> E[0,3]
S[1,0] -> F[1,1] -> C[1,2] -> S[1,3]
A[2,0] -> D[2,1] -> E[2,2] -> E[2,3]
↑ at (2,1)

Why: Last letter matches, word found

Result:

Word found following path:
(0,0)A -> (0,1)B -> (0,2)C -> (1,2)C -> (2,2)E -> (2,1)D

Annotated Code

DSA C

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define ROWS 3
#define COLS 4

bool backtrack(char board[ROWS][COLS], int row, int col, const char *word, int index, bool visited[ROWS][COLS]) {
    if (index == strlen(word)) {
        return true; // All letters matched
    }
    if (row < 0 || row >= ROWS || col < 0 || col >= COLS) {
        return false; // Out of bounds
    }
    if (visited[row][col]) {
        return false; // Already used this cell
    }
    if (board[row][col] != word[index]) {
        return false; // Letter does not match
    }

    visited[row][col] = true; // Mark cell as used

    // Explore neighbors: up, down, left, right
    bool found = backtrack(board, row - 1, col, word, index + 1, visited) ||
                 backtrack(board, row + 1, col, word, index + 1, visited) ||
                 backtrack(board, row, col - 1, word, index + 1, visited) ||
                 backtrack(board, row, col + 1, word, index + 1, visited);

    if (!found) {
        visited[row][col] = false; // Backtrack
    }
    return found;
}

bool exist(char board[ROWS][COLS], const char *word) {
    bool visited[ROWS][COLS] = {false};
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            if (backtrack(board, i, j, word, 0, visited)) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    char board[ROWS][COLS] = {
        {'A','B','C','E'},
        {'S','F','C','S'},
        {'A','D','E','E'}
    };
    const char *word = "ABCCED";

    if (exist(board, word)) {
        printf("Word '%s' found in the grid.\n", word);
    } else {
        printf("Word '%s' NOT found in the grid.\n", word);
    }
    return 0;
}

if (index == strlen(word)) { return true; }

Check if all letters matched, success condition

if (row < 0 || row >= ROWS || col < 0 || col >= COLS) { return false; }

Stop if out of grid bounds

if (visited[row][col]) { return false; }

Avoid revisiting same cell in current path

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

Current cell letter must match current word letter

visited[row][col] = true;

Mark current cell as used

bool found = backtrack(...) || backtrack(...) || backtrack(...) || backtrack(...);

Try all four directions recursively

if (!found) { visited[row][col] = false; }

Backtrack if no path found from here

for (int i = 0; i < ROWS; i++) { for (int j = 0; j < COLS; j++) { if (backtrack(...)) return true; } }

Try starting from every cell in the grid

Output

Word 'ABCCED' found in the grid.

Complexity Analysis

Time: O(N * 3^L) where N is total cells and L is word length, because from each cell we explore up to 3 directions recursively for each letter

Space: O(L) for recursion stack and visited tracking proportional to word length

vs Alternative: Naive search checking all paths without pruning would be much slower; backtracking prunes invalid paths early

Edge Cases

Empty word

Returns true immediately since empty word is trivially found

DSA C

if (index == strlen(word)) { return true; }

Word longer than total cells

Returns false quickly as no path can cover more letters than cells

DSA C

Implicitly handled by recursion depth and visited checks

Word with repeated letters requiring revisiting cells

Does not reuse cells in same path due to visited array, preventing invalid matches

DSA C

if (visited[row][col]) { return false; }

When to Use This Pattern

When asked to find a path or sequence in a grid with constraints on movement and no reuse of cells, use backtracking to explore all valid paths efficiently.

Common Mistakes

Mistake: Not marking cells as visited before recursive calls, causing infinite loops or revisiting
Fix: Mark visited before recursion and unmark after if path fails (backtracking)

Mistake: Checking out-of-bounds after accessing board cell, causing errors
Fix: Check boundaries before accessing board cells

Summary

Finds if a word exists in a grid by moving stepwise in four directions without reusing cells.

Use when searching for sequences in grids with adjacency and no cell reuse constraints.

The key is to try all paths and backtrack when a path does not lead to a solution.

Practice

1. What is the main purpose of using backtracking in a word search grid problem?

easy

A. To sort the grid alphabetically before searching

B. To explore all possible paths to find the word in the grid

C. To count the number of words in the grid

D. To replace characters in the grid with a placeholder

Solution

1. Step 1: Understand backtracking in grid search

   Backtracking tries all possible paths from a starting point to find the target word.

2. Step 2: Compare options with backtracking purpose

   Only To explore all possible paths to find the word in the grid describes exploring all paths, which matches backtracking's goal.

3. Final Answer:

   To explore all possible paths to find the word in the grid -> Option B

4. Quick Check:

   Backtracking = explore all paths [OK]

Hint: Backtracking means trying all paths step-by-step [OK]

Common Mistakes:

• Thinking backtracking sorts or counts words
• Confusing backtracking with simple search
• Assuming backtracking modifies the grid permanently

2. Which of the following is the correct way to check if a cell (row, col) is inside the grid boundaries in C?

easy

A. if (row >= 1 && row < rows && col >= 1 && col < cols)

B. if (row > 0 && row <= rows && col > 0 && col <= cols)

C. if (row > 0 && row < rows && col >= 0 && col <= cols)

D. if (row >= 0 && row < rows && col >= 0 && col < cols)

Solution

1. Step 1: Understand zero-based indexing in C arrays

   Arrays start at index 0, so valid indices are from 0 to rows-1 and 0 to cols-1.

2. Step 2: Check each option for correct boundary conditions

   if (row >= 0 && row < rows && col >= 0 && col < cols) correctly uses >= 0 and < rows/cols. Others use > 0 or <= rows which are incorrect for zero-based arrays.

3. Final Answer:

   if (row >= 0 && row < rows && col >= 0 && col < cols) -> Option D

4. Quick Check:

   Check boundaries with >=0 and < size [OK]

Hint: Use zero-based index: start at 0, less than size [OK]

Common Mistakes:

• Using > 0 instead of >= 0 excludes first row/column
• Using <= rows includes out-of-bound index
• Mixing 1-based and 0-based indexing

3. What will be the output of the following C code snippet for word search backtracking?

char grid[3][3] = {{'A','B','C'},{'D','E','F'},{'G','H','I'}};
int found = searchWord(grid, 3, 3, "BEF");
printf("%d", found);

Assuming searchWord correctly implements backtracking to find the word in the grid.

medium

A. 1

B. 0

C. Compilation error

D. Runtime error

Solution

1. Step 1: Analyze the grid and the word "BEF"

   The grid rows are: ABC, DEF, GHI. The word "BEF" requires letters B, E, F in sequence adjacent horizontally or vertically.

2. Step 2: Check if "BEF" exists in adjacent cells

   B is at (0,1), E is at (1,1), F is at (1,2). B to E is vertical down, E to F is horizontal right, so path exists.

3. Step 3: Confirm if backtracking finds the word

   Backtracking can follow B(0,1) -> E(1,1) -> F(1,2), so word is found.

4. Final Answer:

   1 -> Option A

5. Quick Check:

   Word found = 1 [OK]

Hint: Trace letters stepwise in grid adjacency [OK]

Common Mistakes:

• Assuming letters must be in same row only
• Ignoring vertical or diagonal adjacency rules
• Confusing output 0 and 1 meaning

4. Identify the bug in this backtracking snippet for word search in C:

bool dfs(char grid[][], int row, int col, int index, char* word) {
  if (index == strlen(word)) return true;
  if (row < 0 || row >= rows || col < 0 || col >= cols) return false;
  if (grid[row][col] != word[index]) return false;
  char temp = grid[row][col];
  grid[row][col] = '#';
  bool found = dfs(grid, row+1, col, index+1, word) ||
               dfs(grid, row-1, col, index+1, word) ||
               dfs(grid, row, col+1, index+1, word) ||
               dfs(grid, row, col-1, index+1, word);
  grid[row][col] = temp;
  return found;
}

medium

A. The base case should check index > strlen(word) instead of ==

B. The grid cell is not restored after recursion

C. The grid parameter lacks column size, causing compilation error

D. The function does not check diagonal neighbors

Solution

1. Step 1: Check function parameter declaration

   In C, 2D arrays must have fixed column size in parameters, e.g., char grid[][cols]. Missing column size causes compilation error.

2. Step 2: Verify other parts of the code

   Base case with index == strlen(word) is correct. Grid cell is restored after recursion. Diagonal check is optional, not a bug.

3. Final Answer:

   The grid parameter lacks column size, causing compilation error -> Option C

4. Quick Check:

   2D array params need column size [OK]

Hint: Always specify column size in 2D array parameters [OK]

Common Mistakes:

• Ignoring 2D array parameter syntax in C
• Thinking base case condition is wrong
• Assuming diagonal moves are mandatory

5. Given a 4x4 grid:

{ {'C','A','T','F'},
  {'B','G','E','S'},
  {'I','T','A','E'},
  {'S','O','N','G'} }

Which of the following words can be found using backtracking with adjacent horizontal or vertical moves only?

hard

A. "SONG"

B. "BATS"

C. "CATS"

D. "FATE"

Solution

1. Step 1: Check each word's presence in the grid with adjacency rules

   "SONG": S(3,0), O(3,1), N(3,2), G(3,3) - all adjacent horizontally, so possible.
   "BATS": B(1,0) has no adjacent A (neighbors: C(0,0), I(2,0), G(1,1)), so no.
   "CATS": C(0,0), A(0,1), T(0,2) adjacent, but T(0,2) has no adjacent S (neighbors: A(0,1), F(0,3), E(1,2), A(2,2)), so no.
   "FATE": F(0,3) has no adjacent A (neighbors: T(0,2), S(1,3)), so no.

2. Step 2: Identify which word is fully connected by adjacent moves

   Only "SONG" has all letters adjacent in sequence.

3. Final Answer:

   "SONG" -> Option A

4. Quick Check:

   Check adjacency path for each word [OK]

Hint: Trace letters stepwise horizontally or vertically [OK]

Common Mistakes:

• Assuming diagonal moves allowed
• Ignoring adjacency between letters
• Choosing words with missing adjacent letters