JZ12 矩阵中的路径
描述
请设计一个函数,用来判断在一个n乘m的矩阵中是否存在一条包含某长度为 len 的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。
例如矩阵中包含一条字符串 “bcced” 的路径,但是矩阵中不包含 “abcb” 路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。
数据范围:0 ≤ n,m ≤ 20,1 ≤ len ≤ 25
进阶:时间复杂度O(n2),空间复杂度O(n2 )
示例1
输入:
[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcced"
返回值:
true
示例2
输入:
[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcb"
返回值:
false
解析
初见这种题目,属实有点迷茫。在看了会书后获得了思路,程序的执行逻辑应该为:
- 通过遍历矩阵,以每个位置都作为起点尝试寻找路径;
- 寻找路径时,判断当前节点是否对应上了当前所需字符;
- 若对应上了,则在上下左右四条路径中寻找下一个字符;
- 若四条路径都走不通,说明当前节点其实是个死胡同,此时需要回溯到上一个节点(回溯法,要复原当前节点造成的变化),并返回
false
表明当前节点走不通; - 若四条路径中某条能走通,则在能走通的路径中继续寻找路径,若后续能走通,则当前节点是有效的,可以返回
true
;
- 若四条路径都走不通,说明当前节点其实是个死胡同,此时需要回溯到上一个节点(回溯法,要复原当前节点造成的变化),并返回
- 若没对应上,则说明当前节点走不通,返回
false
; - 若当前节点没有对应的字符,说明路径走完了,寻找到了有效路径,可以返回
true
。
从分析问题时可以注意到,这是一个子结构相似的问题,即都是以某一点探索周围的四条路径,是典型的递归问题。
分析完程序的执行逻辑后,还要进行边界情况的考虑:
- 寻找当前节点周围的四条路径时,若当前节点处于矩阵的边上,则有一条路径是无效的,需要进行判断直接返回
false
,否则会造成数组越界异常; - 题中所述,不能走已经走过的节点,所以需要引入 visited 布尔型数组,大小与矩阵相同,用以表示矩阵中的某个位置是否走过。到达某节点时先进行判断,若该节点已走过,直接返回
false
。
代码清单
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param matrix char字符型二维数组
* @param word string字符串
* @return bool布尔型
*/
// 回溯法
public boolean hasPath (char[][] matrix, String word) {
// 矩阵行数,
int rows = matrix.length;
// 矩阵列数
int cols = matrix[0].length;
// 标记当前为第几个字符
int strNum = 0;
// 方便获取字符
char[] words = word.toCharArray();
// 是否访问过矩阵
boolean[][] visited = new boolean[rows][cols];
// 遍历矩阵,从每个点都开始寻找路径
for(int r = 0;r < rows;r++){
for(int c = 0; c < cols;c++){
if(hasPathCore(matrix,words,strNum,r,c,visited)){
// 找到路了
return true;
}
}
}
// 遍历完都没找到,那就是没有
return false;
}
public boolean hasPathCore(char[][] matrix,char[] words,int strNum,
int row,int col,boolean[][] visited){
// 重要!!!递归停止条件!!!
if( strNum == words.length)
return true;
// 标记
boolean flag = false;
// 矩阵行数,
int rows = matrix.length;
// 矩阵列数
int cols = matrix[0].length;
// 先进行边界情况的判断
if(row<0 || col<0 || row >= rows ||col >= cols || visited[row][col]==true)
return flag;
// 若当前节点走的通!
if(matrix[row][col] == words[strNum]){
// 走下一个点
strNum++;
// 当前点设为走过
visited[row][col] = true;
// 四个方向 寻找后面的路
flag = hasPathCore(matrix,words,strNum,row+1,col,visited)
|| hasPathCore(matrix,words,strNum,row-1,col,visited)
|| hasPathCore(matrix,words,strNum,row,col+1,visited)
|| hasPathCore(matrix,words,strNum,row,col-1,visited);
// 只有能找到后面的路时,这个节点才是有效路径,否则要回溯
if(flag==false){
strNum--;
visited[row][col] = false;
}
}
return flag;
}
}
之前想到的一个疑问:一个节点要找它周围的四条路,有没有可能寻路过程中它们会撞上?
答案是不会,因为递归在程序中其实是按顺序执行的,即按照定义好的方向如上下左右,就会先找上面的路,再到下面的路,以此类推,若当前路径走不通了,则会回溯到之前的状态,不会对后面的寻路造成影响。
总结
第一次写回溯法相关的题目,想不到思路也很正常,但其实还是比较简单的。