时间复杂度

找起点要O(n2)，后面判断应该就是O(m),m为字符串长度

JAVA 代码

class Solution {

    static int count = 0;

    public static boolean hasPath(char[][] matrix, String str) {
        if (matrix == null || str == null || matrix.length <= 0 || str.length() <= 0){
            return false;
        }
        // 先找到所有满足的起点
        char[] target = str.toCharArray();
        char start = target[0];
        boolean flag = false;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == start){
                    int[][] book = new int[matrix.length][matrix[0].length];
                    flag |= hasPath0(matrix,book,target,i,j);
                    if (flag){
                        return true;
                    }
                }
            }
        }
        return flag;
    }

    private static boolean hasPath0(char[][] matrix, int[][] book, char[] target, int x, int y){
        if (book[x][y] != 1 && matrix[x][y] == target[count]){
            book[x][y] = 1;
            count++;
            if (count == target.length){
                return true;
            }else {
                boolean f = false;
                // 往上走
                if (x - 1 >= 0 && y < matrix[0].length){
                    f |= hasPath0(matrix,book,target,x - 1,y);
                }
                // 往右走
                if (!f && x >= 0 && y + 1 < matrix[0].length){
                    f |= hasPath0(matrix,book,target,x,y + 1);
                }
                // 往下走
                if (!f && x + 1 < matrix.length && y < matrix[0].length){
                    f |= hasPath0(matrix,book,target,x + 1,y);
                }
                // 往左走
                if (!f && x >= 0 && y - 1 >= 0){
                    f |= hasPath0(matrix, book, target, x, y - 1);
                }
                // 四个方向均不能满足，则返回到上一层之前需要重置标志位
                if (!f){
                    book[x][y] = 0;
                    count--;
                }
                return f;
            }
        }
        return false;
    }
}