剑指 Offer 12. 矩阵中的路径
请设计一个函数, 用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径. 路径可以从矩阵中的任意一格开始, 每一步可以在矩阵中向左, 右, 上, 下移动一格. 如果一条路径经过了矩阵的某一格, 那么该路径不能再次进入该格子. 例如, 在下面的 3*4 的矩阵中包含一条字符串 "bfce" 的路径 (路径中的字母用加粗标出).
- [["a","b","c","e"],
- ["s","f","c","s"],
- ["a","d","e","e"]]
但矩阵中不包含字符串 "abfb" 的路径, 因为字符串的第一个字符 b 占据了矩阵中的第一行第二个格子之后, 路径不能再次进入这个格子.
示例 1:
输入: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], Word = "ABCCED"
输出: true
示例 2:
输入: board = [["a","b"],["c","d"]], Word = "abcd"
输出: false
提示:
- 1 <= board.length <= 200
- 1 <= board[i].length <= 200
解题思路
以目标字符串的首个字符为起点, 对矩阵进行深度优先遍历即可, 并且在遍历过程中, 将深度优先遍历的深度作为参数传给下一个递归方法, 也就是此遍历深度的字符 与目标字符串的下标的字符 应当相等, 如果不相等, 应当进行剪枝, 搜索下一个位置.
- private boolean[][] visit;
- private int row;
- private int colume;
- private int[][] delta;
- public boolean exist(char[][] board, String Word) {
- // 定义矩阵 DFS 遍历的四个方向
- delta = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
- row = board.length;
- colume = board[0].length;
- // DFS 遍历需要的访问数组
- visit = new boolean[row][colume];
- for (int i = 0; i <row; i++) {
- for (int j = 0; j < colume; j++) {
- if (Word.charAt(0) == board[i][j]) {
- // 根据字符串首字幕找到起点
- if (dfs(board, Word, 0, i, j)) {
- return true;
- }
- }
- }
- }
- return false;
- }
- public boolean dfs(char[][] board, String Word, int index, int x, int y) {
- // 只有相同的字符才会进入到搜索过程
- if (Word.charAt(index) == board[x][y]) {
- if (index == Word.length() - 1) {
- return true;
- }
- visit[x][y] = true;
- for (int i = 0; i < 4; i++) {
- int newx = x + delta[i][0];
- int newy = y + delta[i][1];
- if ((newx>= 0 && newx <row && newy>= 0 && newy < colume) &&
- !visit[newx][newy] &&
- dfs(board, Word, index + 1, newx, newy)) {
- return true;
- }
- }
- }
- // 否则, 直接返回 false 进行剪枝
- visit[x][y] = false;
- return false;
- }
来源: http://www.bubuko.com/infodetail-3716906.html