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

Recall & Review

beginner

What is the main idea behind using backtracking for word search in a grid?

Backtracking tries to build the word by exploring each possible path in the grid step-by-step, and if a path does not lead to the word, it goes back (undoes) and tries another path.

beginner

In the word search problem, why do we mark cells as visited during backtracking?

We mark cells as visited to avoid using the same cell more than once in the current word path, preventing cycles and incorrect matches.

beginner

What are the typical directions explored from a cell in a word search grid using backtracking?

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

intermediate

How does backtracking ensure all possible paths are checked in the grid?

Backtracking recursively explores each valid neighbor cell for the next character, and if a path fails, it backtracks to try other neighbors until all options are exhausted.

beginner

What is the base case for the recursive backtracking function in word search?

The base case is when all characters of the word have been matched successfully, meaning the word is found in the grid.

Which of the following is NOT a valid move direction in a typical word search backtracking?

A Up

B Down

C Diagonal

D Left

Typical word search problems consider only up, down, left, and right moves, not diagonal moves.

Why do we need to mark cells as visited during backtracking in word search?

A To speed up the search

B To avoid revisiting the same cell in the current path

C To store the word found so far

D To count the number of words

Marking cells as visited prevents using the same cell multiple times in the current word path.

What happens if the current path does not match the word during backtracking?

A The algorithm backtracks and tries other paths

B The algorithm skips the word

C The algorithm stops immediately

D The algorithm marks the word as found

Backtracking undoes the current step and tries other possible paths to find the word.

What is the time complexity of word search using backtracking in an m x n grid for a word of length k?

A O(m + n + k)

B O(m * n)

C O(k^2)

D O(m * n * 4^k)

Each cell can lead to up to 4 directions, so worst case is O(m * n * 4^k).

What is the base case in the recursive backtracking function for word search?

A When the word is fully matched

B When the grid is empty

C When no neighbors are left

D When the first character is found

The base case is when all characters in the word have been matched successfully.

Explain how backtracking works to find a word in a grid step-by-step.

Think about trying paths and undoing steps when stuck.

Describe why marking cells as visited is important in word search backtracking.

Imagine walking on a path and not stepping on the same stone twice.

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