题解 | #童谣寻找问题#

这个问题可以使用回溯法来解决。我们可以遍历整个网格，对于每个单元格，如果它的字母与 word 的第一个字母相同，就从这个单元格开始进行深度优先搜索。在搜索过程中，我们需要记录哪些单元格已经被访问过，以防止重复使用同一个单元格。

public class Solution {
    private boolean dfs(char[][] board, boolean[][] visited, int i, int j,
                        int index, String word) {
        // end condition
        if (board[i][j] != word.charAt(index) ) return false;
        if (index == word.length() - 1) return true;
        
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        boolean result = false;

        visited[i][j] = true; //处理节点
        for (int[] dir : directions) {
            int newx = i + dir[0], newy = j + dir[1];
            if (newx >= 0 && newy >= 0 && newx < board.length && newy < board[0].length) {
                if (!visited[newx][newy]) {
                    boolean flag = dfs(board, visited, newx, newy, index + 1, word) ;
                    if(flag){
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false; //撤销处理
        return result;
    }

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

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