面试题12. 矩阵中的路径

解题思路：

本问题是典型的矩阵搜索问题，可使用深度优先搜索（DFS）+ 剪枝解决。

算法原理：

深度优先搜索：可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。

剪枝：在搜索中，遇到这条路不可能和目标字符串匹配成功的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为可行性剪枝。

思路参考：jyd

算法流程

递归参数： i，j为将matrix抽象成二维矩阵时当前访问的行列索引； index时当前str待匹配的字符位置；

终止条件：

false：1)当前矩阵访问越界， 2）当前字符串越界，3)当前访问的矩阵中的位置与str中待匹配的位置不匹配。
true：匹配到str最后一个元素，即index == str.length-1

递归工作：

标记当前矩阵元素：判断当前访问元素是否匹配，为防止再次访问，想要将当前的matrix[i * cols + j] 设置成一个新的值；
搜索下一单元格：深度遍历，递归的判断上下左右四个方向是否满足匹配；
还原当前矩阵元素：判断完当前元素的四个方向后，需将matrix[i * cols + j]设置回原来的值；

public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        if(rows * cols <= 0|| str.length < 1) return false;
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                // 找第一个匹配的元素
                if(matrix[i * cols + j] == str[0]){
                    if (dfs(matrix, rows, cols, i, j , str, 0)) return true;
                }
            }
        }
        return false;
    }
    /*
    递归参数： i，j为将matrix抽象成二维矩阵时 当前访问的行列索引； index时当前str待匹配的字符位置；
    终止条件： 
        1）false：1. 当前矩阵访问越界， 2）当前字符串越界 ，3)当前访问的矩阵中的位置与str中待匹配的位置 不匹配。
        2）true： 匹配到str最后一个元素，即index == str.length-1
    递归工作： 1） 标记当前矩阵元素：判断当前访问元素是否匹配， 为防止再次访问，想要将当前的matrix[i * cols + j] 设置成一个新的值；
             2） 搜索下一单元格：  深度遍历，递归的判断上下左右四个方向是否满足匹配；
             3） 还原当前矩阵元素：判断完当前元素的四个方向后，需将matrix[i * cols + j]设置回原来的值；
    */
    boolean dfs(char[] matrix, int rows, int cols, int i, int j ,char[] str, int index){
        if(i < 0 || j <0 || i>= rows || j >= cols|| (i*cols + j) > (rows * cols -1) || index < 0 || matrix[i*cols+j] != str[index]){
            return false;
        }
        if(index >= str.length-1) return true;
        char temp = matrix[i * cols + j];
        matrix[i * cols + j] = '/';
        boolean res = dfs(matrix, rows, cols, i+1, j, str, index+1)||dfs(matrix, rows, cols, i, j-1, str, index+1)||
            dfs(matrix, rows, cols, i-1, j, str, index+1) || dfs(matrix, rows, cols, i, j+1, str, index+1);
        matrix[i * cols + j] = temp;
        return res;
    }

}

复杂度

M,N 分别为矩阵行列大小， K 为字符串 str 长度。

时间复杂度 O(3^KMN)：最差情况下，需要遍历矩阵中长度为 K 字符串的所有方案（搜索中每个字符有上、下、左、右四个方向可以选择，舍弃回头（上个字符）的方向，剩下 3 种选择，因此方案数的复杂度为 O(3^K)O(3 K），时间复杂度为 O(3^K)；矩阵***有 MN 个起点，时间复杂度为O(MN) 。

空间复杂度 O(K) ：搜索过程中的递归深度不超过 K ，因此系统因函数调用累计使用的栈空间占用O(K) （因为函数返回后，系统调用的栈空间会释放）。最坏情况下 K = MN ，递归深度为MN ，此时系统栈使用 O(MN) 的额外空间。