题解 | #矩阵中的路径#

矩阵中的路径

http://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6

题中的主要信息：

矩阵中上下左右随便移动，找到给定字符串的路径
访问可以重复，但是作为路径不能往回走

举一反三：

学习完本题的思路你可以解决如下题目：

JZ13. 机器人的运动范围

方法：递归（推荐使用）

知识点：递归与回溯

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

如果是线型递归，子问题直接回到父问题不需要回溯，但是如果是树型递归，父问题有很多分支，我需要从子问题回到父问题，进入另一个子问题。因此回溯是指在递归过程中，从某一分支的子问题回到父问题进入父问题的另一子问题分支，因为有时候进入第一个子问题的时候修改过一些变量，因此回溯的时候会要求改回父问题时的样子才能进入第二子问题分支。

思路：

要在矩阵中找到从某个位置开始，位置不重复的一条路径，路径为某个字符串，那我们肯定是现在矩阵中找到这个位置的起点。没办法直观的找出来，只能遍历矩阵每个位置都当作起点试一试。

找到起点后，它周围的节点是否可以走出剩余字符串子串的路径，该子问题又可以作为一个递归。因此，可以用递归来解决。

终止条件： 到了矩阵的边界或者是下一个字符与这个位置的字符不匹配，或者字符串匹配完成，都需要返回，
返回值： 将每条查询路径是否有这样的字符串返回，即true or false。
本级任务： 检查这个位置的字符与字符串中这个字符是否匹配，并向与它相邻的四个方向（且不是来的方向）延伸子问题。

dfs(matrix, n, m, i - 1, j, word, k + 1, flag)
||dfs(matrix, n, m, i + 1, j, word, k + 1, flag)
||dfs(matrix, n, m, i, j - 1, word, k + 1, flag)
||dfs(matrix, n, m, i , j + 1, word, k + 1, flag)

同时，在走的过程中，要设置一个和矩阵大小相同的bool矩阵表示是否已经访问，如果某个结点访问了，在同一条路线上就不能再访问了，其他路线依旧可以访问，所以若是某条路线不达标，需要回溯，将其改回来。

flag[i][j] = true;
...//递归
//没找到经过此格的，此格未被占用
flag[i][j] = false;

具体做法：

step 1：优先处理矩阵为空的特殊情况。
step 2：设置flag数组记录某一次路径中矩阵中的位置是否被经过，因此一条路径不能回头。
step 3：遍历矩阵，对每个位置进行递归。
step 4：递归查找的时候，到了矩阵的边界或者是下一个字符与这个位置的字符不匹配，或者节点已经访问过了，或者字符串匹配完成都结束递归。
step 5：访问节点，修改flag数组，向其他四个方向延伸，回溯的时候修改flag数组。

图示：

图片说明

Java实现代码：

import java.util.*;
public class Solution {
    private boolean dfs(char[][] matrix, int n, int m, int i, int j, String word, int k, boolean[][] flag){
        if(i < 0 || i >= n || j < 0 || j >= m || (matrix[i][j] != word.charAt(k)) || (flag[i][j] == true))
            //下标越界、字符不匹配、已经遍历过不能重复
            return false;
        //k为记录当前第几个字符
        if(k == word.length() - 1) 
            return true;
        flag[i][j] = true;
        //该结点任意方向可行就可
        if(dfs(matrix, n, m, i - 1, j, word, k + 1, flag)
          ||dfs(matrix, n, m, i + 1, j, word, k + 1, flag)
          ||dfs(matrix, n, m, i, j - 1, word, k + 1, flag)
          ||dfs(matrix, n, m, i , j + 1, word, k + 1, flag))
            return true; 
        //没找到经过此格的，此格未被占用
        flag[i][j] = false; 
        return false;
    }
    
    public boolean hasPath (char[][] matrix, String word) {
        //优先处理特殊情况
        if(matrix.length == 0)
            return false;
        int n = matrix.length;
        int m = matrix[0].length;
        //初始化flag矩阵记录是否走过
        boolean[][] flag = new boolean[n][m];
        //遍历矩阵找起点
        for(int i = 0; i < n; i++){  
            for(int j = 0; j < m; j++){
                //通过dfs找到路径
                if(dfs(matrix, n, m, i, j, word, 0, flag))
                    return true;
            }
        }
        return false;
    }
}

C++实现代码：

class Solution {
public:
    bool dfs(vector<vector<char> >& matrix, int n, int m, int i, int j, string word, int k, vector<vector<bool> >& flag){
        if(i < 0 || i >= n || j < 0 || j >= m || (matrix[i][j] != word[k]) || (flag[i][j] == true))
            //下标越界、字符不匹配、已经遍历过不能重复
            return false;
        //k为记录当前第几个字符
        if(k == word.length() - 1) 
            return true;
        flag[i][j] = true;
        //该结点任意方向可行就可
        if(dfs(matrix, n, m, i - 1, j, word, k + 1, flag)
          ||dfs(matrix, n, m, i + 1, j, word, k + 1, flag)
          ||dfs(matrix, n, m, i, j - 1, word, k + 1, flag)
          ||dfs(matrix, n, m, i , j + 1, word, k + 1, flag))
            return true; 
        //没找到经过此格的，此格未被占用
        flag[i][j] = false; 
        return false;
    }
    bool hasPath(vector<vector<char> >& matrix, string word) {
        //优先处理特殊情况
        if(matrix.size() == 0)
            return false;
        int n = matrix.size();
        int m = matrix[0].size();
        //初始化flag矩阵记录是否走过
        vector<vector<bool> > flag(n, vector<bool>(m, false)); 
        //遍历矩阵找起点
        for(int i = 0; i < n; i++){  
            for(int j = 0; j < m; j++){
                //通过dfs找到路径
                if(dfs(matrix, n, m, i, j, word, 0, flag))
                    return true;
            }
        }
        return false;
    }
};

Python实现代码：

class Solution:
    def dfs(self, matrix: List[List[str]], n: int, m: int, i: int, j: int, word: str, k: int, flag: List[List[bool]]) -> bool:
        if i < 0 or i >= n or j < 0 or j >= m or (matrix[i][j] != word[k]) or flag[i][j]:
            #下标越界、字符不匹配、已经遍历过不能重复
            return False
        #k为记录当前第几个字符
        if k == len(word) - 1:
            return True
        flag[i][j] = True
        #该结点任意方向可行就可
        if (self.dfs(matrix, n, m, i - 1, j, word, k + 1, flag) 
            or self.dfs(matrix, n, m, i + 1, j, word, k + 1, flag) 
            or self.dfs(matrix, n, m, i, j - 1, word, k + 1, flag) 
            or self.dfs(matrix, n, m, i , j + 1, word, k + 1, flag)):
            return True 
        #没找到经过此格的，此格未被占用
        flag[i][j] = False 
        return False

    def hasPath(self , matrix: List[List[str]], word: str) -> bool:
        if len(matrix) == 0:
            return False
        n = len(matrix)
        m = len(matrix[0])
        #初始化flag矩阵记录是否走过
        flag = [[False for i in range (m)] for j in range(n)]
        #遍历矩阵找起点
        for i in range(n):
            for j in range(m):
                #通过dfs找到路径
                if self.dfs(matrix, n, m, i, j, word, 0, flag):
                    return True
        return False

复杂度分析：

时间复杂度： $O (m n * 3^{k})$ ，其中 $m$ 与 $n$ 为矩阵的边长， $k$ 为字符串的长度，遍历一次矩阵，每次条递归最坏遍历深度为 $k$ ，看起来是四个方向，但是有一个方向是来的方向不重复访问，所以是三叉树型递归，因此递归复杂度为 $O (k^{3})$
空间复杂度： $O (m n)$ ，辅助二维数组记录是否走过某节点使用了空间