回溯算法

时间复杂度$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;
    }
}