每天一道剑指offer-矩形中的路径
矩形中的路径
题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
解析
定义一个黑盒 hasPathCorechar(matrix,rows,cols,inti,intj,str,index)，表示从 rows行 cols列的矩阵 matrix中的 (i,j)位置开始走是否能走出一条与 str的子串 index~str.length-1相同的路径。那么对于当前位置 (i,j)，需要关心的只有一下三点：
(i,j)是否越界了(i,j)上的字符是否和str[index]匹配(i,j)是否已在之前走过的路径上
如果通过了上面三点检查，那么认为 (i,j)这个位置是可以走的，剩下的就是 (i,j)上下左右四个方向能否走出 str的 index+1~str.length-1，这个交给黑盒就好了。
还有一点要注意，如果确定了可以走当前位置 (i,j)，那么需要将该位置的 visited标记为 true，表示该位置在已走过的路径上，而退出 (i,j)的时候（对应下面第 32行）又要将他的 visited重置为 false。
public boolean hasPath(char[] matrix, int rows, int cols, char[] str){
if(matrix == null || matrix.length != rows * cols || str == null){
return false;
}
boolean[] visited = new boolean[matrix.length];
for(int i = 0 ; i < rows ; i++){
for(int j = 0 ; j < cols ; j++){
//以矩阵中的每个点作为起点尝试走出str对应的路径
if(hasPathCore(matrix, rows, cols, i, j, str, 0, visited)){
return true;
}
}
}
return false;
}
//当前在矩阵的(i,j)位置上//index -> 匹配到了str中的第几个字符
private boolean hasPathCore(char[] matrix, int rows, int cols, int i, int j, char[] str, int index, boolean[] visited){
if(index == str.length){
return true;
}
//越界或字符不匹配或该位置已在路径上
if(!match(matrix, rows, cols, i, j, str[index]) || visited[i * cols + j] == true){
return false;
}
visited[i * cols + j] = true;
boolean res = hasPathCore(matrix, rows, cols, i + 1, j, str, index + 1, visited) || hasPathCore(matrix, rows, cols, i - 1, j, str, index + 1, visited) || hasPathCore(matrix, rows, cols, i, j + 1, str, index + 1, visited) || hasPathCore(matrix, rows, cols, i, j - 1, str, index + 1, visited);
visited[i * cols + j] = false; return res;
}
//矩阵matrix中的(i,j)位置上是否是c字符
private boolean match(char[] matrix, int rows, int cols, int i, int j, char c){
if(i < 0 || i > rows - 1 || j < 0 || j > cols - 1){
return false;
}
return matrix[i * cols + j] == c;
}出自：http://www.zhenganwen.top
已获授权
举报
腾讯云开发者
