Word Search - LeetCode Solution in Java

1. Introduction

The "Word Search" problem is about finding a specific word in a 2D grid of characters. The word must be formed by sequentially adjacent cells (horizontally or vertically), and each cell can be used only once in the construction of the word.

2. Problem

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

3. Solution Steps

1. Iterate over each cell in the grid.

2. Use a recursive function to check if the current cell starts the word.

3. Explore in all four directions (up, down, left, right) for the next character.

4. Mark the cell as visited by altering its content temporarily.

5. If the word is found, return true.

6. Backtrack by restoring the cell's original content.

7. Continue the search until all cells are explored or the word is found.

4. Solution in Java

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

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

    board[i][j] ^= 256; // Mark the cell as visited
    boolean exists = search(board, i + 1, j, word, index + 1) ||
                     search(board, i - 1, j, word, index + 1) ||
                     search(board, i, j + 1, word, index + 1) ||
                     search(board, i, j - 1, word, index + 1);
    board[i][j] ^= 256; // Backtrack: Restore the cell's original content
    return exists;
}

This solution uses depth-first search (DFS) with backtracking to explore possible paths in the grid that might form the given word, ensuring no cell is used more than once in the construction of a word.

Explanation:

1. The exist method iterates over each cell in the board.

2. The search method is called to check if the current cell matches the first character of the word.

3. The method then recursively checks in all four directions for the next character.

4. A cell is temporarily marked as visited by changing its content (board[i][j] ^= 256).

5. If the word is completely found (index == word.length()), return true.

6. The search function backtracks if the current path does not lead to the solution, restoring the cell's original content.

7. The process continues until all paths are explored or the word is found.