Word Search in Grid Using Backtracking in DSA C++ - Execution Trace

Concept Flow - Word Search in Grid Using Backtracking

Start at each cell in grid

↓

Check if cell matches first letter of word

↓

If match, start backtracking

↓

Explore neighbors (up, down, left, right)

↓

Check if next letter matches and not visited

↓

If matches, recurse deeper

↓

If full word matched

→Return True

↓

If no match or dead end

→Backtrack: unmark visited

↓

Try next neighbor or next cell in grid

↓

If all cells tried and no match

→Return False

The search starts from each cell, tries to match the word by moving in four directions using backtracking, marking visited cells to avoid reuse, and backtracks on dead ends.

Execution Sample

DSA C++

bool backtrack(vector<vector<char>>& board, string& word, int i, int j, int index) {
  if (index == word.size()) return true;
  if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != word[index]) return false;
  char temp = board[i][j];
  board[i][j] = '#'; // mark visited
  bool found = backtrack(board, word, i + 1, j, index + 1) ||
               backtrack(board, word, i - 1, j, index + 1) ||
               backtrack(board, word, i, j + 1, index + 1) ||
               backtrack(board, word, i, j - 1, index + 1);
  board[i][j] = temp; // unmark visited
  return found;
}

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

This code tries to find the word in the grid by starting backtracking from each cell.

Execution Table

Step	Operation	Current Position (row,col)	Word Index	Visited Cells	Action	Visual State
1	Start search	-	-	{}	Check cell (0,0)	[A, B, C] [D, E, F] [G, H, I]
2	Match first letter	(0,0)	0	{(0,0)}	Match 'A', move to neighbors	[*A*, B, C] [D, E, F] [G, H, I]
3	Explore neighbor	(0,1)	1	{(0,0),(0,1)}	Match 'B', move to neighbors	[*A*, *B*, C] [D, E, F] [G, H, I]
4	Explore neighbor	(0,2)	2	{(0,0),(0,1),(0,2)}	Match 'C', word complete	[*A*, *B*, *C*] [D, E, F] [G, H, I]
5	Return True	-	-	-	Word found	[*A*, *B*, *C*] [D, E, F] [G, H, I]

💡 Word matched fully at step 4, search ends successfully.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
Current Position	-	(0,0)	(0,1)	(0,2)	-
Word Index	0	0	1	2	-
Visited Cells	{}	{(0,0)}	{(0,0),(0,1)}	{(0,0),(0,1),(0,2)}	-

Key Moments - 3 Insights

Why do we mark cells as visited during backtracking?

Marking cells as visited prevents revisiting the same cell in the current path, avoiding infinite loops and incorrect matches. See execution_table rows 2-4 where visited cells grow.

What happens if a neighbor cell does not match the next letter?

Backtracking stops exploring that path and unmarks the visited cell to try other neighbors or start from a different cell. This is implied in the flow after step 4 if no match is found.

Why do we start backtracking from every cell in the grid?

Because the word can start anywhere, we must try each cell as a potential start. This is shown in the concept_flow and the initial loops in the code.

Visual Quiz - 3 Questions

Look at the execution_table, what is the set of visited cells at step 3?

A {(0,0),(0,1)}

B {(0,1)}

C {(0,0)}

D {}

💡 Hint

Check the 'Visited Cells' column at step 3 in the execution_table.

At which step does the word get fully matched according to the execution_table?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look for the step where 'word complete' is mentioned in the 'Action' column.

If the first letter does not match at (0,0), what happens next?

A Backtracking starts from (0,0) anyway

B Search ends immediately

C Search moves to next cell (0,1)

D Word is found by skipping letters

💡 Hint

Refer to the concept_flow where search tries each cell if no match at current.

Concept Snapshot

Word Search in Grid Using Backtracking:
- Start from each cell in grid
- Match letters sequentially moving up/down/left/right
- Mark cells visited to avoid reuse
- Backtrack on dead ends
- Return true if full word matched
- Return false if no path found

Full Transcript

This concept shows how to find a word in a grid by starting from each cell and using backtracking to explore neighbors. We mark cells visited to avoid revisiting in the same path. If a letter matches, we move to neighbors for the next letter. If a path fails, we backtrack and try other paths. The search ends when the full word is matched or all cells are tried without success.

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