Word Search - Java Solution

1. Introduction

In this post, we delve into a classic problem often encountered in algorithms and puzzles: the "Word Search". The challenge is to determine whether a given word can be found in a grid of characters, where the word can be formed by sequentially adjacent cells, either horizontally or vertically.

Problem

Given a 2D grid of characters and a string word, the task is to return true if word exists in the grid. A word is said to exist if it can be constructed from letters of sequentially adjacent cells, where adjacent cells are either horizontally or vertically neighboring. Importantly, the same cell cannot be used more than once.

2. Solution Steps

1. Iterate over each cell in the grid.

2. If the first letter of the word matches the cell, start a depth-first search (DFS) from that cell.

3. In the DFS, check each neighboring cell to see if the subsequent letters match.

4. Mark visited cells to avoid revisiting them during the search.

5. If the entire word is found, return true.

6. If the end of the grid is reached without finding the word, return false.

3. Code Program

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

    // Function to check if the word exists in the grid
    public static boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == word.charAt(0) && dfs(board, i, j, 0, word)) {
                    return true;
                }
            }
        }
        return false;
    }

    // Helper function for depth-first search
    private static boolean dfs(char[][] board, int i, int j, int count, String word) {
        if (count == word.length()) {
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[i].length || board[i][j] != word.charAt(count)) {
            return false;
        }
        char temp = board[i][j];
        board[i][j] = ' '; // Mark the cell as visited
        boolean found = dfs(board, i + 1, j, count + 1, word)
                    || dfs(board, i - 1, j, count + 1, word)
                    || dfs(board, i, j + 1, count + 1, word)
                    || dfs(board, i, j - 1, count + 1, word);
        board[i][j] = temp; // Reset the cell
        return found;
    }
}

Output:

true

Explanation:

1. exist: This function iterates over each cell in the grid. If a cell matches the first letter of the word, it initiates a DFS from that cell.

2. dfs: A recursive depth-first search function that checks the adjacent cells for subsequent letters of the word. It returns true if the word is found.

3. The DFS marks cells as visited by temporarily changing their value. After the DFS call, the cell's original value is restored.

4. The function returns true if the word is found in any path starting from a matching first letter; otherwise, it returns false.

5. The approach ensures that each cell is used only once in the construction of the word.