Example: Word Search - rFronteddu/general_wiki GitHub Wiki

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

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

To solve the Word Search problem, you can use Depth-First Search (DFS) to explore each cell in the grid to see if you can find the given word by moving horizontally or vertically to adjacent cells. Here's the step-by-step Java solution:

Steps:

• Initialize a DFS Function: Create a helper function dfs to perform the depth-first search from a given cell. Use boundary checks to ensure the search does not go out of bounds. Check if the current cell matches the current character of the word. If the word is found, return true. Otherwise, continue the search to adjacent cells (up, down, left, right).
• Mark Cells as Visited: Temporarily mark the current cell as visited by modifying its value to avoid revisiting it during the search. Restore the original value after exploring all possible paths from the current cell.
• Iterate Over the Grid: Iterate over each cell in the grid and initiate a DFS search if the cell's character matches the first character of the word.

public class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word.charAt(0) && dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    private boolean dfs(char[][] board, String word, int i, int j, int index) {
        if (index == word.length()) {
            return true;
        }
        
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index)) {
            return false;
        }
        
        char temp = board[i][j];
        board[i][j] = '#';  // Mark the cell as visited
        
        boolean found = dfs(board, word, i + 1, j, index + 1)
                     || dfs(board, word, i - 1, j, index + 1)
                     || dfs(board, word, i, j + 1, index + 1)
                     || dfs(board, word, i, j - 1, index + 1);
        
        board[i][j] = temp;  // Restore the original value
        
        return found;
    }
}