递归回溯,先找到当前字符,然后分别从当前位置的上下左右去找下一个,找到继续找,找不到返回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; } }