image.png

解法

class Solution {
    public boolean exist(char[][] board, String word) {
        int row = board.length;
        int col = board[0].length;
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                // 以数组中的每个元素为起点，进行遍历
                if (dfs(board, visited, i, j, 0, word)) {
                    return true;
                }
            }
        }
        return false;
    }
  
    private boolean dfs(char[][] board, boolean[][] visited, int i, int j, int k, String word) {
        int row = board.length;
        int col = board[0].length;
        if (i < 0 || i > row - 1) {
            return false;
        }
        if (j < 0 || j > col - 1) {
            return false;
        }
        // 已经访问过 或者 当前访问的不等于word对应位置的元素
        if (visited[i][j] || board[i][j] != word.charAt(k)) {
            return false;
        }
        visited[i][j] = true;
        k++;
        if (k == word.length()) {
            return true;
        }
       // 深度优先遍历
        int[][] forwards = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int[] forward : forwards) {
            if (dfs(board, visited, i + forward[0], j + forward[1], k, word)) {
                return true;
            }
        }
        // 走到这，说明这个节点的分支都走了，并且没有成功的
        // 这种情况下进行回溯
        visited[i][j] = false;
        return false;
    }
}