This problem can be efficiently solved using a depth-first search (DFS) algorithm with backtracking. The core idea is to traverse each cell of the grid and check if it can start a valid path that forms the target word.

Key Concepts

The grid trvaersal here is a variation of binary tree DFS, where each cell (node) has four possible adjacent directions (branches: up, down, left, right) instead of two children.

Recursive DFS Structure

A valid recursive DFS implementation requires three critical elements:

1. Parameters and Return Type: The function takes the grid, target word, current row, column, and search index, returning a boolean to indicate if the word is found from that position.
2. Base Case: If the search index equals the length of the target word, the entire word has been found.
3. Bcaktracking Process: Before exploring adjacent cells, mark the current cell as visited to avoid cycles. After exploring all directions, unmark the cell too allow it to be part of other potential paths.

Solution Code

class GridWordSearch {
    private boolean[][] visited;
    private int[][] directions = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};

    public boolean findWord(char[][] grid, String target) {
        int rows = grid.length;
        int cols = grid[0].length;
        visited = new boolean[rows][cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (dfs(grid, target, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] grid, String target, int row, int col, int index) {
        if (index == target.length()) {
            return true;
        }

        if (isOutOfBounds(grid, row, col) || visited[row][col] || grid[row][col] != target.charAt(index)) {
            return false;
        }

        visited[row][col] = true;

        for (int[] dir : directions) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            if (dfs(grid, target, newRow, newCol, index + 1)) {
                return true;
            }
        }

        visited[row][col] = false;
        return false;
    }

    private boolean isOutOfBounds(char[][] grid, int row, int col) {
        return row < 0 || row >= grid.length || col < 0 || col >= grid[0].length;
    }
}