class Solution {
    /**
    We try to match the word character by character by exploring neighbors.
    At any cell (i, j):
        - If it matches word[index], we try all 4 directions
        - Move to next index (index + 1)
        - If path fails → backtrack
    */
    public boolean exist(char[][] board, String word) {
        int n = board.length;
        int m = board[0].length;

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(dfs(board, word, i, j, 0)) 
                    return true;
            }
        }
        return false;
    }


    public boolean dfs(char[][] board, String word, int row, int col, int index)
    {
        int n = board.length;
        int m = board[0].length;

        // base case
        if(index == word.length())
            return true;

        // invalid case
        if(row < 0 || col < 0 || row >= n || col >= m || board[row][col] != word.charAt(index)) 
        {
            return false;
        }

        // mark visited
        char temp = board[row][col];
        board[row][col] = '#';
        
        // explore all 4-directions
        boolean result = dfs(board, word, row+1, col, index+1) ||
                         dfs(board, word, row, col+1, index+1) ||
                         dfs(board, word, row-1, col, index+1) ||
                         dfs(board, word, row, col-1, index+1);

        // backtrack
        board[row][col] = temp;
        return result;
    }
}