Introduction to Word Search Problem

The Word Search problem presents a captivating challenge in the realm of programming and algorithm design. You are given a grid of characters and a string that represents a word. The objective is to determine whether the word can be formed by connecting adjacent cells in the grid, where "adjacent" means horizontally or vertically neighboring cells.

Imagine a scenario where you have a 2D grid like this:

A B C E
S F C S
A D E E

If you want to find the word "ABCCED," the answer would be true because you can trace the path:

1. (0, 0) -> 'A'
2. (0, 1) -> 'B'
3. (1, 1) -> 'C'
4. (1, 2) -> 'C'
5. (0, 2) -> 'E'
6. (0, 3) -> 'D'

However, if you’re searching for "SEE," the path would be:

1. (2, 2) -> 'S'
2. (2, 1) -> 'E'
3. (2, 0) -> 'E'

The answer would be true as well.

Problem Constraints

1. The grid can contain any lowercase alphabetical characters.
2. You can only move vertically or horizontally from a cell to build the word.
3. Cells can be visited multiple times, but the letters must be used in their respective order.

The Approach: Recursion and Backtracking

Key Concepts Explained

Recursion allows us to explore all possible paths in the grid one step at a time, while backtracking ensures that we can retrace our steps if we hit a dead end. The idea is to try matching each character of the word starting from the grid cells and moving in all potential directions until we either find the word or exhaust the possibilities.

Algorithm Steps

1. Base Case: If the length of the word is zero, it means we've found a match.
2. Out of Bound Check: If we move beyond the grid’s boundaries or revisit a cell, terminate that path.
3. Matching Characters: Check if the current cell matches the current character of the word.
4. Explore Neighbors: Recur for adjacent cells to find the next character in the word.
5. Backtrack: After exploring, mark the cell as unvisited (or use another strategy to indicate it's available again).

Implementation in Java

Let's implement this approach in Java:

public class WordSearch {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || word == null || word.length() == 0) {
            return false;
        }

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

    private boolean dfs(char[][] board, String word, int x, int y, int index) {
        // Base case: if the whole word is found
        if (index == word.length()) {
            return true;
        }
        
        // Out of bounds or unmatched character
        if (x < 0 || x >= board.length || 
            y < 0 || y >= board[0].length || 
            board[x][y] != word.charAt(index)) {
            return false;
        }
        
        // Temporarily mark the cell as visited
        char temp = board[x][y];
        board[x][y] = '#'; // Mark as visited
        
        // Explore all four directions
        boolean found = dfs(board, word, x + 1, y, index + 1) || // Down
                        dfs(board, word, x - 1, y, index + 1) || // Up
                        dfs(board, word, x, y + 1, index + 1) || // Right
                        dfs(board, word, x, y - 1, index + 1);   // Left
        
        // Backtrack - unmark the cell
        board[x][y] = temp;
        
        return found;
    }

    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)); // Output: true

        word = "SEE";
        System.out.println(ws.exist(board, word)); // Output: true

        word = "ABCB";
        System.out.println(ws.exist(board, word)); // Output: false
    }
}

Explanation of the Code

1. exist Method: The main method that checks for each cell in the grid to see if it can be the start of the word.
2. dfs Method: This function recurses into the grid; it checks if the current cell matches the current character of the word and explores adjacent cells.
3. Marking the Cell: Cells are temporarily marked with a placeholder ('#') to prevent revisiting during the current path's exploration.

Conclusion

As we've seen, the Word Search problem gracefully employs the principles of recursion and backtracking to navigate a 2D grid and solve a fundamental problem that frequently pops up in coding interviews and competitions.

Putting this algorithm into practice is a great way to sharpen your problem-solving skills while strengthening your understanding of advanced data structures and algorithms. Happy coding!