解题思路

深度优先搜索 回溯

class Solution {
    //用来标识四个方向
    private int[][] d = {{-1,0},{0,1},{1,0},{0,-1}};
    private int m,n;   //m n 标识平面的尺寸
    private boolean[][] visited;   //标识每个元素是否被访问过
    //判断下标是否越界
    private boolean inArea(int x,int y){
        return x>=0&&x<m&&y>=0&&y<n;
    }
    //从board[startx][starty]开始，寻找word[index....word.size()]
    private boolean searchWord(char[][] board,String word,int index,int startx,int starty){
        //如果找到了最后一个字符 则判断最后一个字符是否匹配
        if(index==word.length()-1)
            return board[startx][starty] == word.charAt(index);
        //首先判断当前元素是否与单词对应的元素匹配
        if(board[startx][starty] ==  word.charAt(index)){
            //设定该元素已经访问过
            visited[startx][starty]=true;
            //向四个方向出发去寻找
            for(int i=0;i<4;i++){
                //设定新的元素的下标
                int newx = startx + d[i][0];
                int newy = starty + d[i][1];
                //首先判断新的下标是否越界 然后确保之前没有访问过
                if(inArea(newx,newy)&&!visited[newx][newy]){
                    //递归地进行seach 此时单词下标+1 使用的是新的坐标
                    //如果寻找成功 返回true
                    if(searchWord(board,word,index+1,newx,newy)){
                        return true;
                    }
                }
            }
            //如果四个方向上都没有找到 则回溯 标识该元素没有被访问过
            visited[startx][starty]=false;
        }
        //不匹配直接返回false
        return false;
    }
    public boolean exist(char[][] board, String word) {
        //声明平面的大小
        m = board.length;
        n = board[0].length;
        //初始化访问数组
        visited = new boolean[m][n];
        //遍历数组 尝试从平面的每一个元素来寻找word
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[i].length;j++)
                //首先从下标为0的单词元素开始寻找
                if(searchWord(board,word,0,i,j))
                    return true;
        }
        //如果下面遍历完之后都没有找到 则返回false
        return false;
    }
}