题解 | #重建二叉树#

递归回溯，先找到当前字符，然后分别从当前位置的上下左右去找下一个，找到继续找，找不到返回false
因为不能路径重复，设置一个标记二维数组，标记走过的位置。

public boolean hasPath (char[][] matrix, String word) {
        if(matrix.length==0||matrix[0].length==0){
            return false;
        }
        boolean flag[][]=new boolean[matrix.length][matrix[0].length];
        // write code here
//先寻找首字符
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                if(matrix[i][j]==word.charAt(0)){//找到进行递归搜索
                    if(search(matrix,word,0,i,j,flag)){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public boolean search(char[][] matrix,String word,int index,int x,int y,boolean flag[][]){
        if(index==word.length()){//当前字符串已经遍历结束
            return true;
        }
        if(x<0||x>=matrix.length||y<0||y>=matrix[0].length||matrix[x][y]!=word.charAt(index)||flag[x][y]){//边界条件以及剪枝
            return false;
        }
        flag[x][y]=true;//递归
       boolean b=search(matrix,word,index+1,x,y-1,flag)||search(matrix,word,index+1,x,y+1,flag)
            ||search(matrix,word,index+1,x-1,y,flag)||search(matrix,word,index+1,x+1,y,flag);
        flag[x][y]=false;//回溯
        return b;
    }
}