回溯算法
时间复杂度$O(n^3)$
Java 代码
class Solution {
public boolean hasPath(char[][] matrix, String str) {
if(str.length() <= 0 || matrix.length <= 0 || matrix[0].length <= 0) {
return false;
}
for(int i = 0; i < matrix[0].length; i++) {
for(int j = 0; j < matrix.length; j++) {
if(goNext(matrix,str,0,i,j)) return true;
}
}
return false;
}
public boolean goNext(char[][] matrix, String str, int cur, int x, int y) {
if(x < 0 || x > matrix[0].length-1 || y < 0 || y > matrix.length-1
|| cur >= str.length() || str.charAt(cur) != matrix[y][x]) {
return false;
}
if(cur == str.length()-1) {
return true;
}
char tmp = matrix[y][x];
// System.out.print(tmp + " ");
// 标记为走过
matrix[y][x] = '.';
char ch = str.charAt(cur);
if(goNext(matrix,str,cur+1,x,y-1) || goNext(matrix,str,cur+1,x,y+1)
|| goNext(matrix,str,cur+1,x-1,y) || goNext(matrix,str,cur+1,x+1,y)) {
return true;
}
// 回溯,注意不能移动到上面那个if语句里,因为可能走不进去
matrix[y][x] = tmp;
return false;
}
}