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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Word Search Result for Simple Grid

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

DSA Java

public class WordSearch {
    public static boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (backtrack(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean backtrack(char[][] board, String word, int i, int j, int index) {
        if (index == word.length()) return true;
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != word.charAt(index)) return false;

        char temp = board[i][j];
        board[i][j] = '#';

        boolean 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;
        return found;
    }

    public static void main(String[] args) {
        char[][] board = {
            {'C', 'A', 'T'},
            {'X', 'Z', 'Y'},
            {'B', 'O', 'T'}
        };
        System.out.println(exist(board, "CAT"));
    }
}

A true

B false

C Compilation error

D Runtime exception

💡 Hint

Trace the search starting from each cell and check if the word "CAT" can be formed by moving horizontally or vertically.

The word "CAT" can be found starting at board[0][0] moving right to board[0][1] and then board[0][2]. The backtracking returns true.

❓ Predict Output

intermediate

Output when Word is Not Present in Grid

What will be the output of the following Java code when searching for the word "DOG" in the given grid?

DSA Java

public class WordSearch {
    public static boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (backtrack(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean backtrack(char[][] board, String word, int i, int j, int index) {
        if (index == word.length()) return true;
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != word.charAt(index)) return false;

        char temp = board[i][j];
        board[i][j] = '#';

        boolean 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;
        return found;
    }

    public static void main(String[] args) {
        char[][] board = {
            {'C', 'A', 'T'},
            {'X', 'Z', 'Y'},
            {'B', 'O', 'T'}
        };
        System.out.println(exist(board, "DOG"));
    }
}

A true

B false

C Compilation error

D Runtime exception

💡 Hint

Check if the letters D, O, G appear in sequence horizontally or vertically in the grid.

The word "DOG" cannot be formed from adjacent letters in the grid, so the method returns false.

🧠 Conceptual

advanced

Understanding Backtracking in Word Search

In the backtracking approach for word search, why do we temporarily mark the current cell as visited (e.g., with '#') before exploring neighbors?

A To mark cells that contain the first letter of the word

B To permanently remove the letter from the grid so it cannot be used again in any search

C To speed up the search by skipping cells with '#' in future searches

D To avoid revisiting the same cell in the current search path and prevent infinite loops

💡 Hint

Think about what happens if the algorithm revisits the same cell while searching for the word.

Marking the cell temporarily prevents revisiting it in the current path, avoiding cycles and incorrect matches. After exploring, the original letter is restored.

🔧 Debug

advanced

Identify the Bug in Word Search Backtracking Code

What is the bug in the following backtracking code snippet for word search that causes incorrect results?

DSA Java

private static boolean backtrack(char[][] board, String word, int i, int j, int index) {
    if (index == word.length()) return true;
    if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) return false;
    if (board[i][j] != word.charAt(index)) return false;

    board[i][j] = '#';

    boolean 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);

    return found;
}

A The original letter is not restored after backtracking, corrupting the grid for other paths

B The base case for index == word.length() should return false instead of true

C The boundary checks are incorrect and cause ArrayIndexOutOfBoundsException

D The function does not check if the current cell is already visited before marking

💡 Hint

Check what happens to the grid after marking a cell as '#' and before returning.

The code marks the cell as '#' but never restores the original letter after exploring neighbors. This corrupts the grid and causes wrong results in other search paths.

🚀 Application

expert

Count All Occurrences of a Word in Grid Using Backtracking

Given a grid and a word, which code snippet correctly counts all distinct occurrences of the word in the grid using backtracking (moving horizontally or vertically)?

A

int count = 0;
for (int i = 0; i < board.length; i++) {
    for (int j = 0; j < board[0].length; j++) {
        count += backtrackCount(board, word, i, j, 0);
    }
}
return count;

private static int backtrackCount(char[][] board, String word, int i, int j, int index) {
    if (index == word.length()) return 1;
    if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) return 0;
    if (board[i][j] != word.charAt(index)) return 0;

    int total = backtrackCount(board, word, i + 1, j, index + 1) +
                backtrackCount(board, word, i - 1, j, index + 1) +
                backtrackCount(board, word, i, j + 1, index + 1) +
                backtrackCount(board, word, i, j - 1, index + 1);

    return total;
}

B

int count = 0;
for (int i = 0; i < board.length; i++) {
    for (int j = 0; j < board[0].length; j++) {
        if (backtrack(board, word, i, j, 0)) count++;
    }
}
return count;

private static boolean backtrack(char[][] board, String word, int i, int j, int index) {
    if (index == word.length()) return true;
    if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != word.charAt(index)) return false;

    char temp = board[i][j];
    board[i][j] = '#';

    boolean 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;
    return found;
}

C

int count = 0;
for (int i = 0; i < board.length; i++) {
    for (int j = 0; j < board[0].length; j++) {
        count += backtrackCount(board, word, i, j, 0);
    }
}
return count;

private static int backtrackCount(char[][] board, String word, int i, int j, int index) {
    if (index == word.length()) return 1;
    if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != word.charAt(index)) return 0;

    char temp = board[i][j];
    board[i][j] = '#';

    int total = backtrackCount(board, word, i + 1, j, index + 1) +
                backtrackCount(board, word, i - 1, j, index + 1) +
                backtrackCount(board, word, i, j + 1, index + 1) +
                backtrackCount(board, word, i, j - 1, index + 1);

    board[i][j] = temp;
    return total;
}

D

int count = 0;
for (int i = 0; i < board.length; i++) {
    for (int j = 0; j < board[0].length; j++) {
        if (backtrackCount(board, word, i, j, 0)) count++;
    }
}
return count;

private static boolean backtrackCount(char[][] board, String word, int i, int j, int index) {
    if (index == word.length()) return true;
    if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != word.charAt(index)) return false;

    board[i][j] = '#';

    boolean found = backtrackCount(board, word, i + 1, j, index + 1) ||
                    backtrackCount(board, word, i - 1, j, index + 1) ||
                    backtrackCount(board, word, i, j + 1, index + 1) ||
                    backtrackCount(board, word, i, j - 1, index + 1);

    board[i][j] = word.charAt(index);
    return found;
}

💡 Hint

Counting all occurrences requires summing all successful paths, not just checking if one exists.

Option C correctly sums all paths that form the word by returning 1 for each complete match and 0 otherwise, while restoring the grid state after each path.

Practice

1. What is the main purpose of backtracking in the Word Search problem on a grid?

easy

A. To sort the grid alphabetically

B. To explore all possible paths to find the word

C. To count the number of words in the grid

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 searching paths for the word.

3. Final Answer:

   To explore all possible paths to find the word -> Option B

4. Quick Check:

   Backtracking = Explore paths [OK]

Hint: Backtracking means trying all paths until word found [OK]

Common Mistakes:

• Thinking backtracking sorts or modifies the grid
• Confusing backtracking with simple search
• Assuming backtracking counts words instead of searching

2. Which of the following Java method signatures correctly represents a backtracking helper for word search in a grid?

easy

A. boolean backtrack(char[][] board, String word, int index, int row, int col)

B. void backtrack(char[] board, String word, int index)

C. int backtrack(char[][] board, String word, int row, int col)

D. String backtrack(char[][] board, String word, int index, int row, int col)

Solution

1. Step 1: Check method parameters

   The method needs the board (2D char array), the word, current index in word, and current position (row, col) to explore.

2. Step 2: Check return type

   Backtracking returns boolean to indicate if word is found along this path.

3. Final Answer:

   boolean backtrack(char[][] board, String word, int index, int row, int col) -> Option A

4. Quick Check:

   Correct signature = boolean backtrack(char[][] board, String word, int index, int row, int col) [OK]

Hint: Backtracking returns boolean and needs position + index [OK]

Common Mistakes:

• Using 1D array instead of 2D for board
• Wrong return type like int or String
• Missing index or position parameters

3. Given the grid:

[['A','B','C','E'],
 ['S','F','C','S'],
 ['A','D','E','E']]

and the word "ABCCED", what will the backtracking function return?

medium

A. throws Exception

B. false

C. null

D. true

Solution

1. Step 1: Trace the word in the grid

   The word "ABCCED" can be found by path: A(0,0) -> B(0,1) -> C(0,2) -> C(1,2) -> E(2,2) -> D(2,1).

2. Step 2: Backtracking confirms path exists

   Since the path exists without revisiting cells, backtracking returns true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Word found = true [OK]

Hint: Trace path step-by-step to confirm word presence [OK]

Common Mistakes:

• Assuming word is not found without checking all directions
• Confusing similar letters in different positions
• Ignoring backtracking's ability to explore multiple paths

4. Consider this backtracking snippet for word search:

if (row < 0 || col < 0 || row >= board.length || col >= board[0].length || board[row][col] != word.charAt(index)) {
    return false;
}

What is the main issue if we forget to mark visited cells during recursion?

medium

A. The function may revisit the same cell causing infinite loops

B. The function will always return true

C. The function will throw an ArrayIndexOutOfBoundsException

D. The function will skip valid paths

Solution

1. Step 1: Understand visited marking role

   Marking visited cells prevents revisiting the same cell in the current path, avoiding cycles.

2. Step 2: Consequence of missing visited marking

   Without marking, recursion may revisit cells endlessly, causing infinite loops or stack overflow.

3. Final Answer:

   The function may revisit the same cell causing infinite loops -> Option A

4. Quick Check:

   Missing visited mark = infinite loops [OK]

Hint: Always mark visited cells to avoid loops [OK]

Common Mistakes:

• Assuming no visited marking is safe
• Confusing out-of-bound checks with visited logic
• Thinking missing visited causes exceptions instead of loops

5. You want to find if the word "SEE" exists in the grid:

[['A','B','C','E'],
 ['S','F','E','S'],
 ['A','D','E','E']]

Using backtracking, which approach correctly handles multiple possible paths and avoids revisiting cells?

hard

A. Only search in one direction (right) to reduce complexity

B. Modify the board characters to '*' when visited and never revert them

C. Use a boolean visited[][] array to mark cells during recursion and backtrack by unmarking after recursion returns

D. Use a global counter to limit recursion depth

Solution

1. Step 1: Understand visited marking with backtracking

   Using a boolean visited array allows marking cells as visited during recursion and unmarking them after exploring all paths from that cell.

2. Step 2: Evaluate other options

   Modifying board permanently breaks original data, searching only right misses paths, and limiting recursion depth does not solve revisiting.

3. Final Answer:

   Use a boolean visited[][] array to mark cells during recursion and backtrack by unmarking after recursion returns -> Option C

4. Quick Check:

   Visited array + backtrack unmark = correct approach [OK]

Hint: Mark visited with boolean array and unmark after recursion [OK]

Common Mistakes:

• Permanently changing board characters
• Ignoring directions other than right
• Using recursion limits instead of visited marking