Word Search in Grid Using Backtracking in DSA Java

Mental Model

We try to find the word by exploring each letter step-by-step in the grid, going back if a path doesn't work.

Analogy: Like searching for a hidden path in a maze, you try one direction, and if it leads to a dead end, you go back and try another way.

Grid example:
A B C E
S F C S
A D E E

We look for word 'ABCCED' by moving through adjacent letters.

Dry Run Walkthrough

Input: Grid: [['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], word: 'ABCCED'

Goal: Find if the word 'ABCCED' exists by moving horizontally or vertically in the grid.

Step 1: Start at cell (0,0) with letter 'A' matching first letter of word

Visited: (0,0)
Path: A
Grid:
[A] B C E
S F C S
A D E E

Why: We need to find the first letter to start the search

Step 2: Move right to (0,1) with letter 'B' matching second letter

Visited: (0,0), (0,1)
Path: A -> B
Grid:
A [B] C E
S F C S
A D E E

Why: Next letter must be adjacent and match the word

Step 3: Move right to (0,2) with letter 'C' matching third letter

Visited: (0,0), (0,1), (0,2)
Path: A -> B -> C
Grid:
A B [C] E
S F C S
A D E E

Why: Continue matching letters in order

Step 4: Move down to (1,2) with letter 'C' matching fourth letter

Visited: (0,0), (0,1), (0,2), (1,2)
Path: A -> B -> C -> C
Grid:
A B C E
S F [C] S
A D E E

Why: Next letter must be adjacent vertically or horizontally

Step 5: Move down to (2,2) with letter 'E' matching fifth letter

Visited: (0,0), (0,1), (0,2), (1,2), (2,2)
Path: A -> B -> C -> C -> E
Grid:
A B C E
S F C S
A D [E] E

Why: Keep following the word letters

Step 6: Move left to (2,1) with letter 'D' matching sixth letter

Visited: (0,0), (0,1), (0,2), (1,2), (2,2), (2,1)
Path: A -> B -> C -> C -> E -> D
Grid:
A B C E
S F C S
A [D] E E

Why: Last letter matches, word found

Result:

Word found with path:
(0,0) A -> (0,1) B -> (0,2) C -> (1,2) C -> (2,2) E -> (2,1) D

Annotated Code

DSA Java

public class WordSearch {
    private static final int[][] DIRECTIONS = {{-1,0},{1,0},{0,-1},{0,1}};

    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        if (rows == 0) return false;
        int cols = board[0].length;
        boolean[][] visited = new boolean[rows][cols];

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (board[r][c] == word.charAt(0)) {
                    if (backtrack(board, word, 0, r, c, visited)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean backtrack(char[][] board, String word, int index, int row, int col, boolean[][] visited) {
        if (index == word.length()) {
            return true; // All letters matched
        }

        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length ||
            visited[row][col] || board[row][col] != word.charAt(index)) {
            return false; // Out of bounds or letter mismatch or already visited
        }

        visited[row][col] = true; // Mark current cell as visited

        for (int[] dir : DIRECTIONS) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            if (backtrack(board, word, index + 1, newRow, newCol, visited)) {
                return true; // Found valid path
            }
        }

        visited[row][col] = false; // Backtrack: unmark cell
        return false; // No path found from this cell
    }

    public static void main(String[] args) {
        WordSearch ws = new WordSearch();
        char[][] board = {
            {'A','B','C','E'},
            {'S','F','C','S'},
            {'A','D','E','E'}
        };
        String word = "ABCCED";
        System.out.println(ws.exist(board, word));
    }
}

if (board[r][c] == word.charAt(0)) {

Start search only from cells matching first letter

if (backtrack(board, word, 0, r, c, visited)) {

Try to find word starting from this cell

if (index == word.length()) { return true; }

All letters matched, word found

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

Stop if out of bounds, visited, or letter mismatch

visited[row][col] = true;

Mark current cell as part of path

for (int[] dir : DIRECTIONS) { int newRow = row + dir[0]; int newCol = col + dir[1]; if (backtrack(board, word, index + 1, newRow, newCol, visited)) { return true; } }

Explore all four directions recursively

visited[row][col] = false;

Backtrack: unmark cell to allow other paths

Output

true

Complexity Analysis

Time: O(N * 3^L) because we start from each cell (N) and explore up to 3 directions for each letter in word length L

Space: O(L) for recursion stack and visited tracking for word length L

vs Alternative: Naive search without backtracking would be inefficient and may revisit cells causing exponential blowup; backtracking prunes invalid paths early

Edge Cases

Empty grid

Returns false immediately as no letters to match

DSA Java

int rows = board.length; if rows == 0, return false immediately

Word longer than total cells

Returns false because word cannot fit

DSA Java

if (index == word.length()) return true; base case prevents overrun

Word with repeated letters requiring backtracking

Backtracking correctly explores alternate paths

DSA Java

visited[row][col] = false; // backtrack unmarking

When to Use This Pattern

When asked to find a path or sequence in a grid with constraints on movement and no reuse of cells, use backtracking to explore all possible paths efficiently.

Common Mistakes

Mistake: Not marking visited cells causing revisiting and infinite loops
Fix: Use a visited array to mark cells during current path and unmark on backtrack

Mistake: Checking out-of-bound indices after accessing array causing errors
Fix: Check boundaries before accessing grid cells

Summary

Finds if a word exists in a grid by moving horizontally or vertically using backtracking.

Use when searching for sequences in grids with movement and no cell reuse allowed.

The key is to try each path and backtrack when a path does not lead to a solution.

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