Word Search in Grid Using Backtracking in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Word Search Result

What is the output of the following C++ code that checks if the word "CAT" exists in the given grid using backtracking?

DSA C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool dfs(vector<vector<char>>& board, string& word, int i, int j, int index) {
    if (index == word.size()) return true;
    if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size() || board[i][j] != word[index]) return false;
    char temp = board[i][j];
    board[i][j] = '#';
    bool found = dfs(board, word, i+1, j, index+1) || dfs(board, word, i-1, j, index+1) || dfs(board, word, i, j+1, index+1) || dfs(board, word, i, j-1, index+1);
    board[i][j] = temp;
    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 (dfs(board, word, i, j, 0)) return true;
        }
    }
    return false;
}

int main() {
    vector<vector<char>> board = {
        {'C', 'A', 'T'},
        {'X', 'Z', 'T'},
        {'Y', 'O', 'T'}
    };
    string word = "CAT";
    cout << (exist(board, word) ? "Found" : "Not Found") << endl;
    return 0;
}

A Compilation Error

B Not Found

C Found

D Runtime Error

💡 Hint

Trace the DFS starting from each cell and check if the word "CAT" can be formed by moving up, down, left, or right.

The word "CAT" can be found starting at board[0][0] = 'C', then board[0][1] = 'A', and board[0][2] = 'T'. The DFS returns true, so output is "Found".

❓ Predict Output

intermediate

Output of Word Search with No Match

What is the output of the following C++ code that checks if the word "DOG" exists in the given grid using backtracking?

DSA C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool dfs(vector<vector<char>>& board, string& word, int i, int j, int index) {
    if (index == word.size()) return true;
    if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size() || board[i][j] != word[index]) return false;
    char temp = board[i][j];
    board[i][j] = '#';
    bool found = dfs(board, word, i+1, j, index+1) || dfs(board, word, i-1, j, index+1) || dfs(board, word, i, j+1, index+1) || dfs(board, word, i, j-1, index+1);
    board[i][j] = temp;
    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 (dfs(board, word, i, j, 0)) return true;
        }
    }
    return false;
}

int main() {
    vector<vector<char>> board = {
        {'C', 'A', 'T'},
        {'X', 'Z', 'T'},
        {'Y', 'O', 'T'}
    };
    string word = "DOG";
    cout << (exist(board, word) ? "Found" : "Not Found") << endl;
    return 0;
}

A Not Found

B Compilation Error

C Runtime Error

D Found

💡 Hint

Check if the letters 'D', 'O', 'G' appear in sequence in the grid.

The word "DOG" cannot be formed from the given grid by moving up, down, left, or right. So the output is "Not Found".

🔧 Debug

advanced

Identify the Bug in Word Search Backtracking

The following code is intended to find if a word exists in a grid using backtracking. However, it sometimes returns incorrect results. What is the bug?

DSA C++

#include <vector>
#include <string>
using namespace std;

bool dfs(vector<vector<char>>& board, string& word, int i, int j, int index) {
    if (index == word.size()) return true;
    if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size() || board[i][j] != word[index]) return false;
    board[i][j] = '#';
    bool found = dfs(board, word, i+1, j, index+1) || dfs(board, word, i-1, j, index+1) || dfs(board, word, i, j+1, index+1) || dfs(board, word, i, j-1, index+1);
    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 (dfs(board, word, i, j, 0)) return true;
        }
    }
    return false;
}

A The DFS should also check diagonal neighbors.

B The code does not restore the original character after DFS, causing wrong results.

C The base case should check if index > word.size(), not ==.

D The board should be passed by value, not by reference.

💡 Hint

Think about what happens to the board cells after marking them visited.

The code marks a cell as '#' to indicate visited but does not restore it after DFS calls. This corrupts the board for other paths, causing incorrect results.

❓ Predict Output

advanced

Output of Word Search with Repeated Letters

What is the output of the following C++ code that checks if the word "TOT" exists in the given grid using backtracking?

DSA C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool dfs(vector<vector<char>>& board, string& word, int i, int j, int index) {
    if (index == word.size()) return true;
    if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size() || board[i][j] != word[index]) return false;
    char temp = board[i][j];
    board[i][j] = '#';
    bool found = dfs(board, word, i+1, j, index+1) || dfs(board, word, i-1, j, index+1) || dfs(board, word, i, j+1, index+1) || dfs(board, word, i, j-1, index+1);
    board[i][j] = temp;
    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 (dfs(board, word, i, j, 0)) return true;
        }
    }
    return false;
}

int main() {
    vector<vector<char>> board = {
        {'T', 'O', 'T'},
        {'O', 'T', 'O'},
        {'T', 'O', 'T'}
    };
    string word = "TOT";
    cout << (exist(board, word) ? "Found" : "Not Found") << endl;
    return 0;
}

A Found

B Not Found

C Compilation Error

D Runtime Error

💡 Hint

Look for the word "TOT" starting from multiple positions and consider backtracking.

The word "TOT" can be found in multiple paths in the grid. The DFS finds at least one valid path, so output is "Found".

🧠 Conceptual

expert

Time Complexity of Word Search Backtracking

What is the worst-case time complexity of the backtracking algorithm used to find a word of length k in an m x n grid?

A O(m * n * k^4)

B O(4^(m * n))

C O(k * m * n)

D O(m * n * 4^k)

💡 Hint

Consider that from each cell, you explore up to 4 directions for each character in the word.

At each of the k characters, the algorithm explores up to 4 directions from each cell. Since there are m*n starting cells, worst-case complexity is O(m * n * 4^k).

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