请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子
1条回答 默认 最新
关注 /** 用一个状态数组保存之前访问过的字符,然后再分别按上,下,左,右递归 */ public class Solution { public boolean hasPath(char[] matrix, int rows, int cols, char[] str) { int flag[] = new int[matrix.length]; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (helper(matrix, rows, cols, i, j, str, 0, flag)) return true; } } return false; } private boolean helper(char[] matrix, int rows, int cols, int i, int j, char[] str, int k, int[] flag) { int index = i * cols + j; if (i < 0 || i >= rows || j < 0 || j >= cols || matrix[index] != str[k] || flag[index] == 1) return false; if(k == str.length - 1) return true; flag[index] = 1; if (helper(matrix, rows, cols, i - 1, j, str, k + 1, flag) || helper(matrix, rows, cols, i + 1, j, str, k + 1, flag) || helper(matrix, rows, cols, i, j - 1, str, k + 1, flag) || helper(matrix, rows, cols, i, j + 1, str, k + 1, flag)) { return true; } flag[index] = 0; return false; } }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥15 求lingo代码和思路
- ¥15 公交车和无人机协同运输
- ¥15 stm32代码移植没反应
- ¥15 matlab基于pde算法图像修复,为什么只能对示例图像有效
- ¥100 连续两帧图像高速减法
- ¥15 如何绘制动力学系统的相图
- ¥15 对接wps接口实现获取元数据
- ¥20 给自己本科IT专业毕业的妹m找个实习工作
- ¥15 用友U8:向一个无法连接的网络尝试了一个套接字操作,如何解决?
- ¥30 我的代码按理说完成了模型的搭建、训练、验证测试等工作(标签-网络|关键词-变化检测)