Word Search in Grid Using Backtracking in DSA C++

Mental Model

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

Analogy: Imagine searching for a hidden path in a maze by trying each direction and backtracking when you hit a dead end.

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

Start at any cell matching first letter, then 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 without revisiting cells.

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

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 to start the search

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

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

Why: Next letter must be adjacent horizontally or vertically

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

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 letters in order

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

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: Move vertically to next letter

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

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: Continue matching letters

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

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 matched, word found

Result:

Visited cells form path: (0,0)->(0,1)->(0,2)->(1,2)->(2,2)->(2,1)
Word 'ABCCED' found in grid

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int rows = board.size();
        if (rows == 0) return false;
        int cols = board[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == word[0]) {
                    if (backtrack(board, word, visited, i, j, 0)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

private:
    bool backtrack(vector<vector<char>>& board, const string& word, vector<vector<bool>>& visited, int row, int col, int index) {
        if (index == word.size()) {
            return true; // all letters matched
        }
        if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size()) {
            return false; // out of bounds
        }
        if (visited[row][col] || board[row][col] != word[index]) {
            return false; // already visited or letter mismatch
        }

        visited[row][col] = true; // mark current cell visited

        // explore all 4 directions
        bool found = backtrack(board, word, visited, row + 1, col, index + 1) ||
                     backtrack(board, word, visited, row - 1, col, index + 1) ||
                     backtrack(board, word, visited, row, col + 1, index + 1) ||
                     backtrack(board, word, visited, row, col - 1, index + 1);

        visited[row][col] = false; // backtrack: unmark cell

        return found;
    }
};

int main() {
    vector<vector<char>> board = {
        {'A','B','C','E'},
        {'S','F','C','S'},
        {'A','D','E','E'}
    };
    string word = "ABCCED";

    Solution sol;
    bool result = sol.exist(board, word);
    cout << (result ? "Word found" : "Word not found") << endl;
    return 0;
}

for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (board[i][j] == word[0]) {

start search from cells matching first letter

if (backtrack(board, word, visited, i, j, 0)) { return true;

if backtracking finds word, return true

if (index == word.size()) { return true;

all letters matched, success

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

stop if out of grid bounds

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

stop if cell visited or letter mismatch

visited[row][col] = true;

mark current cell visited before exploring neighbors

bool found = backtrack(board, word, visited, row + 1, col, index + 1) || backtrack(board, word, visited, row - 1, col, index + 1) || backtrack(board, word, visited, row, col + 1, index + 1) || backtrack(board, word, visited, row, col - 1, index + 1);

explore all four directions recursively

visited[row][col] = false;

unmark cell to allow other paths (backtracking)

Output

Word found

Complexity Analysis

Time: O(N * 3^L) because we start from each cell (N total) and explore up to 3 directions for each letter in word length L

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

vs Alternative: Naive brute force without pruning would be worse; backtracking prunes invalid paths early saving time

Edge Cases

Empty grid or empty word

Returns false immediately since no word can be found

DSA C++

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

Word longer than total cells

Returns false because word cannot fit in grid

DSA C++

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

Word with repeated letters requiring careful visited tracking

Backtracking prevents revisiting cells, correctly finds or rejects word

DSA C++

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

When to Use This Pattern

When you need to find a path or sequence in a grid with constraints on movement and no revisits, use backtracking to explore all possibilities step-by-step.

Common Mistakes

Mistake: Not marking cells as visited causing infinite loops or revisiting same cell
Fix: Mark cells visited before recursive calls and unmark after to backtrack

Mistake: Checking out-of-bound indices after accessing grid causing runtime errors
Fix: Check boundaries 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 and no cell reuse allowed.

The key is to explore all paths step-by-step and backtrack when a path fails.

Practice

1. What is the main purpose of backtracking in the Word Search in Grid problem?

easy

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

B. To sort the grid alphabetically before searching

C. To count the number of words in the grid

D. To replace characters in the grid with special symbols

Solution

1. Step 1: Understand backtracking role

   Backtracking tries all possible paths in the grid to find the word by moving in allowed directions and undoing moves if they don't lead to a solution.

2. Step 2: Eliminate other options

   Sorting, counting words, or replacing characters are not related to backtracking's purpose in this problem.

3. Final Answer:

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

4. Quick Check:

   Backtracking = Explore paths [OK]

Hint: Backtracking means trying all paths and undoing wrong steps [OK]

Common Mistakes:

• Thinking backtracking sorts or modifies the grid
• Confusing backtracking with simple searching
• Ignoring the undo step in backtracking

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 == 0 && col == 0)

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 grid indexing

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

2. Step 2: Check boundary condition

   if (row >= 0 && row < rows && col >= 0 && col < cols) correctly checks if row and col are within these ranges using && (and) operator.

3. Final Answer:

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

4. Quick Check:

   Boundary check = if (row >= 0 && row < rows && col >= 0 && col < cols) [OK]

Hint: Use >= 0 and < size with && to check boundaries [OK]

Common Mistakes:

• Using > 0 instead of >= 0 excludes first row/column
• Using || instead of && allows invalid indices
• Checking only (0,0) cell

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

char grid[3][3] = {{'A','B','C'},{'D','E','F'},{'G','H','I'}};
string word = "BE";
// Assume function exist: bool exist(char grid[][], string word)
cout << (exist(grid, word) ? "Found" : "Not Found") << endl;

Assuming exist uses backtracking correctly.

medium

A. Found

B. Not Found

C. Compilation Error

D. Runtime Error

Solution

1. Step 1: Analyze grid and word

   The grid is:
   A B C
   D E F
   G H I
   The word is "BE".

2. Step 2: Check if "BE" can be formed

   Starting at 'B' (0,1), next letter 'E' must be adjacent (up, down, left, right). Adjacent cells to 'B' are 'A'(0,0), 'C'(0,2), 'E'(1,1). 'E' is adjacent, so path B->E exists.

3. Step 3: Confirm backtracking finds the word

   Backtracking will find "BE" successfully.

4. Final Answer:

   Found -> Option A

5. Quick Check:

   Word "BE" exists in grid = Found [OK]

Hint: Check adjacency of letters in grid for word presence [OK]

Common Mistakes:

• Ignoring adjacency rules
• Assuming diagonal moves allowed (usually not)
• Confusing output with error

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

bool backtrack(int r, int c, int index) {
  if (index == word.length()) return true;
  if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
  if (grid[r][c] != word[index]) return false;
  grid[r][c] = '#';
  bool found = backtrack(r+1, c, index+1) || backtrack(r-1, c, index+1) || backtrack(r, c+1, index+1) || backtrack(r, c-1, index+1);
  return found;
}

medium

A. Incorrect boundary checks

B. Wrong base case condition

C. Using '||' instead of '&&' in recursive calls

D. Missing restoring grid[r][c] after recursion

Solution

1. Step 1: Understand backtracking marking

   The code marks visited cells by setting grid[r][c] = '#'.

2. Step 2: Check if grid is restored after recursion

   After recursive calls, the original character should be restored to allow other paths. This code does not restore it.

3. Step 3: Identify the bug

   Missing restoration causes wrong results or blocks other paths.

4. Final Answer:

   Missing restoring grid[r][c] after recursion -> Option D

5. Quick Check:

   Restore grid after recursion = Fix bug [OK]

Hint: Always undo changes after recursive calls in backtracking [OK]

Common Mistakes:

• Not restoring visited cells
• Wrong base case logic
• Incorrect boundary conditions

5. Given a 4x4 grid:

char grid[4][4] = {
  {'C','A','T','F'},
  {'B','G','E','S'},
  {'I','T','A','E'},
  {'S','E','R','T'}
};

Which of the following words can be found using backtracking moving only up, down, left, or right?
Select the correct option.

hard

A. "CATS"

B. "TEA"

C. "FEST"

D. "BAT"

Solution

1. Step 1: Check "CATS"

   "CATS" starts at (0,0) 'C', next 'A' at (0,1), next 'T' at (0,2), but no adjacent 'S' to 'T' at (0,2). Adjacent: 'A'(0,1), 'F'(0,3), 'E'(1,2). No path exists.

2. Step 2: Check "TEA"

   "TEA" letters: T, E, A.
   Possible path: (2,1) 'T' -> (3,1) 'E' -> (2,2) 'A' ? From 'E'(3,1) to 'A'(2,2) is diagonal, invalid.
   Try other 'T's: (0,2) 'T' -> (1,2) 'E' down -> (2,2) 'A' down. Valid path.

3. Step 3: Check "FEST" and "BAT"

   "FEST" letters not found in order with adjacency.
   "BAT" letters: B(1,0), A(2,2), T(0,2) no continuous path.

4. Final Answer:

   "TEA" -> Option B

5. Quick Check:

   Check adjacency for each word = "TEA" found [OK]

Hint: Trace letter adjacency step-by-step for each word [OK]

Common Mistakes:

• Assuming diagonal moves allowed
• Not checking letter order carefully
• Ignoring multiple occurrences of letters