leetcode 79. 单词搜索 （java）

谢谢题解

好烦回溯

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(dfs(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }
    private boolean dfs(char[][] board, String word, int i, int j, int id){
        if(i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != word.charAt(id))
            return false;
        if(id == word.length() - 1) return true;

        board[i][j] = '*';
        int[][] distance = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for(int[] d : distance){
            if(dfs(board, word, i + d[0], j + d[1], id + 1)) return true;
        }
        board[i][j] = word.charAt(id);
        return false;
    }
}