79. 单词搜索 (opens new window)

class Solution {
    char[][] board;
    String word;
    int n;
    int[][] dirs = {{1,0},{-1,0},{0,-1},{0,1}};
    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word;
        this.n = word.length();
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(dfs(0,i,j)){
                    return true;
                }
            }
        }
        return false;
    }
    boolean dfs(int idx,int x,int y){
        if(word.charAt(idx)!=board[x][y])
            return false;
        if(idx==n-1)
            return true;
        char ch = board[x][y];
        board[x][y] = '.';
        for(int[] dir:dirs){
            int dx = x+dir[0];
            int dy = y+dir[1];
            if(dx<0||dx>=board.length||dy<0||dy>=board[0].length
            || board[dx][dy]=='.'){
                continue ;
            }
            if(dfs(idx+1,dx,dy))
                return true;
        }
        board[x][y] = ch;
        return false;
    }
}