题目 请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如 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){ 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; } }