推荐

完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-U6HnVH7c-1594719341678)(C:\Users\YX\AppData\Roaming\Typora\typora-user-images\image-20200627101852748.png)]

矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

public class Solution {
   
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
   
    
    }


}

思路： 回溯

1. 因为每个格子只能走一次，所以我们先给每个格子都设置一个标记，初始化为 false，走过的为 false 。
2. 虽然给的是一维数组，但是我们可以通过行数和列数来模拟二维数组遍历数组，然后一个个元素匹配
3. 将这个元素位置转换成一维数组中的位置，然后根据来判断
4. 先判断跳出递归的条件：数组越界，当前位置的元素与字符串中的元素不匹配，当前元素位置已经走过一次了。这几种直接返回 false ，终止这次递归。
5. 如果字符串中的元素已经判断到最后一位且匹配了，说明匹配成功，返回true。
6. 如果当前位置的元素与字符串的元素匹配，但还没有匹配完字符串中元素，那么我们递归检查周围是否有符合的元素。如果有的话，再继续检查一下匹配元素位置周围的元素是否匹配，如此递归检查下去。直到将字符串中的元素匹配完，或者匹配失败。匹配失败的话，要退出这次递归，并回溯，将这次递归中做的操作还原回去。
7. 如果某次递归检查之后，没有完全匹配，结束这次递归的时候，记得要还原标记位。

参考实现：

public class Solution {
   
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
   
        //标志位，初始化位false
        boolean[] flag = new boolean[matrix.length];
        for(int i = 0; i < rows; i++) {
   
            for(int j = 0; j < cols; j++){
   
                if(check(matrix, i, j, rows, cols, flag, str, 0)) {
   
                    return true;
                }
            }
         }
        //遍历完数组也没有找到匹配的路径，返回false
        return false;
    }
    
    /** * * @param matrix 初始化矩阵 * @param i 索引行坐标 * @param j 索引列坐标 * @param rows 矩阵行数 * @param cols 矩阵列数 * @param flag 标记位数组 * @param str 要判断的字符串 * @param k 要判断字符串中的下标 * @return */
    private boolean check(char[] matrix, int i, int j, int rows, int cols, boolean[] flag, char[] str, int k) {
   
        //根据元素的索引行和列坐标，转换成元素在一维数组中的位置。（因为输入给的是一个一维数组）。
        int index = i * cols + j;
        //递归终止条件: 数组越界，字符不匹配，该路径位置上的字符已经使用过了。
        if(i < 0 || j < 0 || i >= rows || j >= cols || matrix[index] != str[k] || flag[index] == true) {
   
            return false;
        }
        
        //路径已经匹配到最后一个字符了，路径匹配成功，返回true
        if(k == str.length - 1) {
   
            return true;
        }
        
        //将路径上的这个位置标记一下，标记为已经走过了，避免下次再走。
        flag[index] = true;
        
        //回溯，递归查找，查找当前字符的上下左右的字符中是否有符合的下一个字符，每次找到之后，将 k+1 继续找下一个，找不到就还原。、
        if (check(matrix, i - 1, j, rows, cols, flag, str, k + 1)
           ||check(matrix, i + 1, j, rows, cols, flag, str, k + 1)
           ||check(matrix, i, j - 1, rows, cols, flag, str, k + 1)
           ||check(matrix, i, j + 1, rows, cols, flag, str, k + 1)
           ) {
   
            return true;
        }
        //如果递归查找之后发现后面的都匹配不了完整的路径，那么还原，尝试其他路径
        flag[index] = false;
        return false;
        
    }

}

看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。

这里是猿兄，为你分享程序员的世界。

非常感谢各位大佬们能看到这里，如果觉得文章还不错的话， 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用！！！

注： 如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！