Word Search in Grid Using Backtracking in DSA C#

Mental Model

We try to find the word by exploring each letter step-by-step in the grid, going back if a path doesn't work.

Analogy: Like searching for a hidden path in a maze by trying each direction and backtracking when hitting a dead end.

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

Start at any cell and move up/down/left/right to find the word.

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 word[0]

Visited: (0,0)
Path: A
Grid:
[A] B C E
S F C S
A D E E

Why: We need to find the first letter of the word to start the search.

Step 2: Move right to cell (0,1) with letter 'B' matching word[1]

Visited: (0,0), (0,1)
Path: A -> B
Grid:
A [B] C E
S F C S
A D E E

Why: Next letter 'B' found adjacent to previous letter.

Step 3: Move right to cell (0,2) with letter 'C' matching word[2]

Visited: (0,0), (0,1), (0,2)
Path: A -> B -> C
Grid:
A B [C] E
S F C S
A D E E

Why: Continue matching next letter in the word.

Step 4: Move down to cell (1,2) with letter 'C' matching word[3]

Visited: (0,0), (0,1), (0,2), (1,2)
Path: A -> B -> C -> C
Grid:
A B C E
S F [C] S
A D E E

Why: Next letter 'C' found vertically adjacent.

Step 5: Move down to cell (2,2) with letter 'E' matching word[4]

Visited: (0,0), (0,1), (0,2), (1,2), (2,2)
Path: A -> B -> C -> C -> E
Grid:
A B C E
S F C S
A D [E] E

Why: Next letter 'E' found vertically adjacent.

Step 6: Move left to cell (2,1) with letter 'D' matching word[5]

Visited: (0,0), (0,1), (0,2), (1,2), (2,2), (2,1)
Path: A -> B -> C -> C -> E -> D
Grid:
A B C E
S F C S
A [D] E E

Why: Last letter 'D' found adjacent, word found.

Result:

Word found: A -> B -> C -> C -> E -> D
Grid with path:
A B C E
S F C S
A D E E

Annotated Code

DSA C#

using System;

class WordSearch {
    static int rows, cols;
    static bool[,] visited;

    public static bool Exist(char[][] board, string word) {
        if (board == null || board.Length == 0 || board[0].Length == 0) return false;
        rows = board.Length;
        cols = board[0].Length;
        visited = new bool[rows, cols];

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (board[r][c] == word[0]) {
                    if (Backtrack(board, word, r, c, 0)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    static bool Backtrack(char[][] board, string word, int r, int c, int index) {
        if (index == word.Length) return true; // found all letters

        if (r < 0 || c < 0 || r >= rows || c >= cols) return false; // out of bounds
        if (visited[r, c]) return false; // already used this cell
        if (board[r][c] != word[index]) return false; // letter mismatch

        visited[r, c] = true; // mark cell visited

        // explore neighbors: up, down, left, right
        bool found = Backtrack(board, word, r - 1, c, index + 1) ||
                     Backtrack(board, word, r + 1, c, index + 1) ||
                     Backtrack(board, word, r, c - 1, index + 1) ||
                     Backtrack(board, word, r, c + 1, index + 1);

        if (!found) {
            visited[r, c] = false; // backtrack
        }

        return found;
    }

    static void Main() {
        char[][] board = new char[][] {
            new char[] {'A','B','C','E'},
            new char[] {'S','F','C','S'},
            new char[] {'A','D','E','E'}
        };
        string word = "ABCCED";
        bool result = Exist(board, word);
        Console.WriteLine(result ? "Word found" : "Word not found");
    }
}

if (board[r][c] == word[0]) {

start search from cells matching first letter

if (Backtrack(board, word, r, c, 0)) {

try to find word starting at this cell

if (index == word.Length) return true;

all letters matched, word found

if (r < 0 || c < 0 || r >= rows || c >= cols) return false;

stop if out of grid bounds

if (visited[r, c]) return false;

avoid revisiting same cell in current path

if (board[r][c] != word[index]) return false;

stop if current letter does not match

visited[r, c] = true;

mark current cell as used

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

explore all four directions recursively

if (!found) { visited[r, c] = false; }

backtrack by unmarking cell if path fails

Output

Word found

Complexity Analysis

Time: O(N * 3^L) where N is total cells and L is word length because each cell can start a search and each step explores up to 3 directions (excluding the previous cell).

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

vs Alternative: Brute force checking all paths without pruning would be much slower; backtracking prunes invalid paths early.

Edge Cases

Empty grid

Returns false immediately as no letters to match

DSA C#

if (board == null || board.Length == 0 || board[0].Length == 0) return false;

Word longer than total cells

Returns false since word cannot fit

DSA C#

if (index == word.Length) return true; (never reached if word too long)

Word with repeated letters requiring backtracking

Backtracking ensures correct path is found or rejected

DSA C#

visited[r, c] = false; // backtrack

When to Use This Pattern

When asked to find a word or pattern in a grid by moving stepwise in multiple directions, use backtracking to explore all paths and backtrack on dead ends.

Common Mistakes

Mistake: Not marking visited cells causing revisiting and infinite loops
Fix: Use a visited structure to mark cells used in current path and unmark on backtrack

Mistake: Checking out-of-bound indices after accessing grid causing errors
Fix: Check boundaries before accessing grid cells

Summary

Finds if a word exists in a grid by exploring adjacent letters using backtracking.

Use when searching for sequences in grids where movement is restricted to neighbors.

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

Practice

1. What is the main purpose of backtracking in the Word Search problem on a grid?

easy

A. To count the number of words in the grid

B. To sort the grid alphabetically

C. To explore all possible paths to find the word

D. To replace characters in the grid

Solution

1. Step 1: Understand backtracking role

   Backtracking tries all possible paths in the grid to find the target word by moving in allowed directions.

2. Step 2: Eliminate other options

   Sorting, counting, or replacing characters are unrelated to the search process using backtracking.

3. Final Answer:

   To explore all possible paths to find the word -> Option C

4. Quick Check:

   Backtracking = Explore paths [OK]

Hint: Backtracking explores paths step-by-step to find the word [OK]

Common Mistakes:

• Thinking backtracking sorts or modifies the grid
• Confusing backtracking with counting words
• Assuming backtracking replaces characters permanently

2. Which of the following is the correct way to check if the next cell is within grid bounds in C#?

easy

A. if (row >= 0 && row < grid.Length && col >= 0 && col < grid[0].Length)

B. if (row > 0 && row <= grid.Length && col > 0 && col <= grid[0].Length)

C. if (row >= 0 && row <= grid.Length && col >= 0 && col <= grid[0].Length)

D. if (row > 0 && row < grid.Length && col > 0 && col < grid[0].Length)

Solution

1. Step 1: Understand grid indexing in C#

   Grid rows and columns are zero-indexed, so valid indices are from 0 to Length-1.

2. Step 2: Check boundary conditions

   if (row >= 0 && row < grid.Length && col >= 0 && col < grid[0].Length) correctly checks if row and col are >= 0 and less than Length, ensuring valid indices.

3. Final Answer:

   if (row >= 0 && row < grid.Length && col >= 0 && col < grid[0].Length) -> Option A

4. Quick Check:

   Bounds check uses >=0 and < Length [OK]

Hint: Use >=0 and < Length for zero-based index checks [OK]

Common Mistakes:

• Using > 0 excludes first row/column
• Using <= Length causes out-of-range errors
• Confusing row and column length checks

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

char[][] grid = {
  new char[] {'A','B','C','E'},
  new char[] {'S','F','C','S'},
  new char[] {'A','D','E','E'}
};
string word = "ABCCED";
bool result = WordSearch(grid, word);
Console.WriteLine(result);

Assuming WordSearch uses backtracking correctly to find the word in the grid.

medium

A. True

B. False

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Analyze the grid and word

   The word "ABCCED" can be found by moving right and down starting at grid[0][0]: A->B->C->C->E->D.

2. Step 2: Confirm backtracking finds the word

   Backtracking explores all paths and will find this sequence, so result is true.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Word found in grid = True [OK]

Hint: Trace word path step-by-step in grid to confirm presence [OK]

Common Mistakes:

• Assuming word is not found without tracing path
• Confusing similar letters in grid
• Ignoring backtracking's ability to explore all paths

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

bool Backtrack(char[][] grid, string word, int index, int row, int col) {
  if (index == word.Length) return true;
  if (row < 0 || row >= grid.Length || col < 0 || col >= grid[0].Length) return false;
  if (grid[row][col] != word[index]) return false;
  char temp = grid[row][col];
  grid[row][col] = '#';
  bool found = Backtrack(grid, word, index + 1, row + 1, col) ||
               Backtrack(grid, word, index + 1, row - 1, col) ||
               Backtrack(grid, word, index + 1, row, col + 1) ||
               Backtrack(grid, word, index + 1, row, col - 1);
  grid[row][col] = temp;
  return found;
}

medium

A. The grid cell is not restored after recursion

B. The function does not check for visited cells properly

C. The base case should check index > word.Length

D. The function does not check grid boundaries before accessing

Solution

1. Step 1: Check visited cell marking

   The code marks visited cells by replacing with '#', which prevents revisiting during recursion.

2. Step 2: Identify missing visited check

   However, the code does not check if the current cell is '#' before comparing with word[index], so it may revisit marked cells incorrectly.

3. Final Answer:

   The function does not check for visited cells properly -> Option B

4. Quick Check:

   Visited check missing = Bug [OK]

Hint: Always check if cell is visited before matching character [OK]

Common Mistakes:

• Forgetting to check if cell is marked visited
• Incorrect base case condition
• Not restoring grid cell after recursion

5. Given a 4x4 grid:

char[][] grid = {
  new char[] {'C','A','T','F'},
  new char[] {'B','G','E','S'},
  new char[] {'I','T','A','E'},
  new char[] {'S','O','N','G'}
};

Which of the following words cannot be found using backtracking moving only up, down, left, or right?

hard

A. "CAT"

B. "GATE"

C. "SONG"

D. "BATS"

Solution

1. Step 1: Check presence of each word

   "CAT" is in first row (C->A->T). "SONG" is in last row (S->O->N->G). "GATE" can be formed by G->A->T->E in middle rows.

2. Step 2: Verify "BATS" formation

   "BATS" requires B->A->T->S. B is at grid[1][0], but no path connects A and T and then S in sequence moving only up/down/left/right without skipping letters.

3. Final Answer:

   "BATS" cannot be found -> Option D

4. Quick Check:

   Word path missing = "BATS" [OK]

Hint: Trace each letter path carefully to confirm word presence [OK]

Common Mistakes:

• Assuming all words are present without path check
• Ignoring movement restrictions (no diagonals)
• Confusing letter positions in grid