public class Solution {
    boolean[][] visited;
    public boolean exist(char[][] board, String word) {
        this.visited = new boolean[board.length][board[0].length];
        boolean res = false;
        for(int x=0;x<board.length;x++){
            for(int y=0;y<board[0].length;y++){
                if(board[x][y] == word.charAt(0)){
                    res = res || dfs(board,word,x,y);
                }
            }
        }
        return res;

    }
    public boolean dfs(char[][] board, String word, int x, int y){
        if(word.length() == 0 ) return true;
        boolean res = false;

        if(x<board.length && x>=0 && y >=0 && y<board[0].length){
            if(word.charAt(0) == board[x][y] && visited[x][y] == false){
                visited[x][y] = true;
                res = dfs(board,word.substring(1,word.length()),x-1,y  ) ||
                        dfs(board,word.substring(1,word.length()),x+1,y  ) ||
                        dfs(board,word.substring(1,word.length()),x  ,y-1) ||
                        dfs(board,word.substring(1,word.length()),x  ,y+1);
                visited[x][y] = false;
                return res;
            }
        }
        return false;
    }
}