题目

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

思路 + 代码

没有接触过类似的题型，因此看了讲解。

题目给出的是待查询的矩阵字符串与对应的行与列。

首先需要转化为矩阵。

然后利用回溯法，起始点依次选择矩阵中的每一个位置，上下左右进行遍历。

需要设置一个哨兵矩阵，记录已经访问的，防止重复访问产生无限循环。思想跟http://sunyunzeng.com/Leetcode-%E5%B2%9B%E5%B1%BF%E6%9C%80%E5%A4%A7%E7%9A%84%E9%9D%A2%E7%A7%AF/类似。

判定成功条件：回溯的路径长度与查询路径长度一致。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class Solution {
    private int[][] next = {{1,0},{-1,0},{0,1},{0,-1}};
    private int rows;
    private int cols;
    
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {    
        if(rows<=0 || cols<=0)
            return false;
        this.rows = rows;
        this.cols = cols;
        char[][] m = getMatrix(matrix);
        boolean[][] visit = new boolean[rows][cols];
        for(int i=0; i<rows; i++)
            for(int j=0; j<cols; j++)
                if(backtrace(m, str, i, j, 0, visit))
                    return true;
        return false;
    }

    private boolean backtrace(char[][] matrix, char[] str, int r, int c, int pathLen, 
                             boolean[][] visit){
        // 边界判断
        if(pathLen==str.length)
            return true;
        if(r<0 || r>rows-1 || c<0 || c>cols-1 || str[pathLen]!=matrix[r][c] || visit[r][c])
            return false;
        // 当前格子设定为已访问，防止重复访问
        visit[r][c] = true;
        for(int[] step: next){
            // 递归回溯，只要找到一个字符满足要求，就返回true
            if(backtrace(matrix, str, r+step[0], c+step[1], pathLen+1, visit))
                return true;
        }
        // 此路不通，格子回归初始状态，重新选择起始格子
        visit[r][c] = false;
        return false;
    }
    // 根据一维字符数组生成二维矩阵
    private char[][] getMatrix(char[] matrix){
        char[][] res = new char[rows][cols];
        int s = 0;
        for(int i=0; i<rows; i++)
            for(int j=0; j<cols; j++){
                res[i][j] = matrix[s];
                s++;
            }
        return res;
    }
}