Word Search in Grid Using Backtracking in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind backtracking in the Word Search problem?

Backtracking tries all possible paths in the grid to find the word by exploring one letter at a time and undoing steps if a path does not lead to a solution.

beginner

In the Word Search problem, why do we mark cells as visited during backtracking?

We mark cells as visited to avoid revisiting the same cell in the current search path, preventing cycles and incorrect matches.

beginner

What directions do we explore from each cell in the Word Search grid?

We explore up, down, left, and right neighbors from each cell to find the next character in the word.

beginner

How does the backtracking function know when it has found the entire word?

When the current index reaches the length of the word, it means all characters have been matched successfully.

intermediate

What is the time complexity of the Word Search backtracking solution in the worst case?

The worst-case time complexity is O(N * 3^L), where N is the number of cells in the grid and L is the length of the word, because from each cell we explore up to 3 directions recursively.

Which of the following is NOT a valid move when searching for the next character in the Word Search grid?

A Move up

B Move diagonally

C Move left

D Move right

Only up, down, left, and right moves are allowed; diagonal moves are not considered.

Why do we backtrack (undo) after exploring a path in the Word Search problem?

A To try other possible paths if the current one fails

B To speed up the search

C To mark the word as found

D To avoid using recursion

Backtracking allows us to explore other paths by undoing the current step if it does not lead to a solution.

What data structure is commonly used to keep track of visited cells in the Word Search backtracking?

A Boolean 2D array

B Stack

C Queue

D Hash map

A boolean 2D array is used to mark cells as visited or not during the search.

If the word length is L, what indicates that the word has been found in the backtracking function?

A Current index is greater than L

B Current index is 0

C Current index is less than L

D Current index equals L

When the current index reaches the word length L, it means all characters have been matched.

What is the first step before starting backtracking in the Word Search problem?

A Sort the grid

B Reverse the word

C Find all starting cells matching the first character

D Mark all cells as visited

We start backtracking from cells that match the first character of the word.

Explain how backtracking works to find a word in a grid.

Think about trying one letter at a time and going back if stuck.

Describe the role of the visited array in the Word Search backtracking algorithm.

Why can't we use the same cell twice in one word search path?

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