class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words=word.toCharArray();
        for(int i=0;i<board.length;++i){
            for(int j=0;j<board[0].length;++j){
                if(dfs(board,i,j,words,0)){
                    return true;
                }
            }
        }
        return false;
    }
    boolean dfs(char[][] board, int row,int column,char[] words,int index){
        if(row<0||row>=board.length||column<0||column>=board[0].length||board[row][column]!=words[index]){
            return false;
        }
        if(index==words.length-1){
            return true;
        }
        board[row][column]='\0';
        boolean result=dfs(board,row-1,column,words,index+1)||dfs(board,row+1,column,words,index+1)||dfs(board,row,column-1,words,index+1)||dfs(board,row,column+1,words,index+1);
        board[row][column]=words[index];
        return result;
    }
}