Understanding Word Search in Java

Introduction & Problem Explanation

The Word Search problem asks us to find if a target string word can be constructed from letters of sequentially adjacent cells in a 2D grid of characters board.

Adjacent cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in spelling out the word. For example, given:
board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ]

• For word = "ABCCED", we start at row 0, col 0 ('A'), move right to 'B', then right to 'C', down to 'C', left to 'E', and down to 'D'. The path exists, so we return true.
• For word = "ABCB", we start at row 0, col 0 ('A'), move right to 'B', right to 'C', but then we cannot move back left to 'B' because we are forbidden from reusing the same cell. No other paths exist, so we return false.

To solve this, we perform a Depth First Search (DFS) starting from every cell in the grid, backtracking to undo our movements when a search path hits a dead end.

The Algorithmic Approach

DFS with In-Place Visited Tracking (O(m * n * 4^L) Time, O(L) Space)

Let m and n be the board dimensions, and L be the length of the target word. For each cell (r, c) on the board, we initiate a recursive DFS search if board[r][c] == word.charAt(0). Here is our DFS helper logic at dfs(r, c, index):

• Base Cases:
  • If index == word.length(), we have matched all characters. Return true.
  • If the cell (r, c) is out-of-bounds, or if board[r][c] != word.charAt(index), the path is invalid. Return false.
• Mark Visited: To prevent reusing the current cell in subsequent recursive branches, we temporarily save the character at board[r][c], then replace it with a sentinel character (e.g., '#'). This avoids needing a separate 2D boolean array, reducing memory usage.
• Explore Neighbors: We recursively check the four adjacent cells: (r+1, c), (r-1, c), (r, c+1), and (r, c-1) with index + 1.
• Backtrack: Once the recursive exploration is complete, we restore the original character back to board[r][c].
• Result: If any of the four adjacent searches return true, we immediately propagate true up. Otherwise, return false.

Step-by-Step Execution Walkthrough

Let's trace the algorithm on a 2 × 2 board: [['A', 'B'], ['C', 'D']] searching for "ABD":

1. Step 1 (Scan Start):
   • Cell (0, 0) is 'A'. Matches word[0]. Start DFS: dfs(r=0, c=0, idx=0).
2. Step 2 (DFS at (0, 0)):
   • Check: board[0][0] == 'A'. Correct.
   • Mark visited: Set board[0][0] = '#'.
   • Recurse neighbors: Call dfs(r=1, c=0, idx=1) (down) and dfs(r=0, c=1, idx=1) (right).
3. Step 3 (Explore Down: (1, 0) - 'C'):
   • Check: board[1][0] == 'C', but word[1] == 'B'. Mismatch. Return false.
4. Step 4 (Explore Right: (0, 1) - 'B'):
   • Check: board[0][1] == 'B'. Matches word[1].
   • Mark visited: Set board[0][1] = '#'.
   • Recurse neighbors: Call dfs(r=1, c=1, idx=2) (down to 'D').
5. Step 5 (Explore Down: (1, 1) - 'D'):
   • Check: board[1][1] == 'D'. Matches word[2].
   • Mark visited: Set board[1][1] = '#'.
   • Recurse neighbors: Call dfs(idx=3).
   • Base Case: idx == 3. Return true!
6. Step 6 (Unwind):
   • All recursive layers propagate true. The board cells are restored to their original characters as the stack unwinds. Return true.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

• board[r][c] = '#';: The visited marking step. Replaces the letter with a symbol that cannot match any alphabet, blocking reuse of the cell.
• boolean found = dfs(...) || dfs(...) || ...: Uses short-circuit boolean evaluation. If the first direction finds the word, remaining directions are skipped, speeding up execution.
• board[r][c] = temp;: The backtrack restore step. Restores the grid letter so that adjacent search paths starting from other cells can use it.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

import java.util.Arrays;

public class WordSearch {

    // DFS + Backtracking: Time O(M * N * 4^L), Space O(L)
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0 || word == null) {
            return false;
        }

        int rows = board.length;
        int cols = board[0].length;

        // Start DFS search from every cell on the board
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (dfs(board, word, 0, r, c)) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean dfs(char[][] board, String word, int index, int r, int c) {
        // Base case: matched all characters of the word
        if (index == word.length()) {
            return true;
        }

        // Boundary checks and mismatch checks
        if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] != word.charAt(index)) {
            return false;
        }

        // 1. Choose: Temporarily mark cell as visited using a sentinel char
        char temp = board[r][c];
        board[r][c] = '#';

        // 2. Explore: Try moving in 4 directions
        boolean found = dfs(board, word, index + 1, r + 1, c) // Down
                     || dfs(board, word, index + 1, r - 1, c) // Up
                     || dfs(board, word, index + 1, r, c + 1) // Right
                     || dfs(board, word, index + 1, r, c - 1); // Left

        // 3. Unchoose: Backtrack by restoring the cell's original character
        board[r][c] = temp;

        return found;
    }

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

        System.out.println("--- Word Search Demonstration ---");
        System.out.println("Grid Board:");
        for (char[] row : board) {
            System.out.println(Arrays.toString(row));
        }
        System.out.println("Target Word: " + word);
        boolean result = solver.exist(board, word);
        System.out.println("Word exists in board: " + result); // Expected: true
    }
}

Conclusion

The Word Search problem demonstrates how backtracking navigates 2D coordinates. By modifying the grid in-place to track visited states and restoring values during backtrack step, we optimize execution speed and save extra memory.