Leetcode79单词搜索

代码：

回溯

class Solution {
    static int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    public boolean exist(char[][] board, String word) {        
        int m = board.length;
        int n = board[0].length;
        if(word.length()>m*n)return false;
        int index = 0;
        for(int i=0;i
            for(int j=0;j
                if(board[i][j]==word.charAt(0)){
                    board[i][j]-='A';
                    if(findNext(i,j,board,word,1)){
                        return true;
                    }
                    board[i][j]+='A';
                }
            }
        }
        return false;
    }
    public boolean findNext(int curx,int cury,char[][] board,String word,int index){
        if(index==word.length()){
            return true;
        }
        int m = board.length;
        int n = board[0].length;
        for(int i=0;i
            int x = curx+dirs[i][0];
            int y = cury+dirs[i][1];
            if(x<0||y<0||x>=m||y>=n){continue;}
            if(board[x][y]==word.charAt(index)){
                board[x][y]-='A';
                if(findNext(x,y,board,word,index+1)){
                    return true;
                }
                board[x][y]+='A';
            }
        }
        return false;
    }
}