题解 | #矩阵中的路径#

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如图片说明矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
示例1
输入：[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcced"
返回值：true

题目分析

在矩阵中获得一条路径，是典型的dfs案例，遍历的开头可以是矩阵中的任意一点，从该点可以向上下左右四个方向递归遍历，直到一些边界情况或找到目标字符串；
dfs的模板为：

dfs(x,y,matrix,path,word){
   if(x,y不符合边界要求) return false;
   if(path与目标字符串相同) return true;
   // 进行选择操作
   if(dfs(x+1,y,matrix,path,word) || dfs(x,y+1,matrix,path,word) 
      dfs(x-1,y,matrix,path,word) || dfs(x,y-1,matrix,path,word))
   // 只要四个方向有符合的就为真
   return true;
   // 回退选择操作
}

解题思路

方法:dfs深度递归
思路：
1.外层需要进行m*n的循环，当matrix[i][j]与目标字符串首部字符相同时，进行dfs；
2.在dfs过程中，需要使用 visited[n][m]来标记是否访问过当前结点，然后进行(x,y)位置的上下左右递归，当递归结果为false时，要回退到上一个结点，则将当前位置的访问标记重新标记为未经过；
3.通过进行一些边界判断和是否已经访问过判断以及目标字符是否相同，来进行剪枝，可以加快dfs的递归过程；
示例1的主要dfs过程如图：
图片说明

代码实现

Java实现

    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int n = matrix.length;
        int m = matrix[0].length;
        // 定义标记访问数组
        boolean[][] visited = new boolean[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                // 比较第一个字符，减少时间
                // 当第一个字符相同时，使用dfs遍历判断
                if(matrix[i][j] == word.charAt(0)){
                    if(hasPath2(matrix, word, visited, i, j, 0)){
                        return true;
                    }
                }
            }
        }
        return false;
    }
     public boolean hasPath2(char[][] matrix, String word, boolean[][] visited, int i, int j, int k) {
         // 剪枝，排除一些非法情况，或者该位置已经被访问过
         if(i<0 || j<0 || i>=matrix.length || j>=matrix[0].length || visited[i][j]) return false;
         // 字符已经遍历到最后且匹配时，表示存在
         if(k == word.length()-1 && matrix[i][j] == word.charAt(k)) return true;
         if(word.charAt(k) == matrix[i][j]){
             // 只有相等才会继续比较
             visited[i][j] = true;
             // 向上下左右四个方向进行dfs
             if(hasPath2(matrix, word, visited, i+1, j, k+1)
             || hasPath2(matrix, word, visited, i-1, j, k+1)
             || hasPath2(matrix, word, visited, i, j+1, k+1)
             || hasPath2(matrix, word, visited, i, j-1, k+1)){
                 return true;
             }else{
                 // 都不满足则直接返回，需要把原来的复原
                 visited[i][j] = false;
                 return false;
             }
         }
         // 不相等直接返回
         return false;
     }

时间复杂度： $O(mnk^3)$ ，首先外层有两层循环，最差情况下需要遍历整个矩阵，在一个循环里面，最多需要进行深度为k（目标字符串长度）的递归，因为从一个确定的位置往下走时，下一个点的可走的位置只剩下3个，所以最多需要进行k^3次递归才能结束此次循环，所以时间复杂度为 $O(mnk^3)$ ；
空间复杂度： $O(mn)$ ，需要mn空间的访问数组来进行标记；

C++实现

    bool hasPath(vector<vector<char> >& matrix, string word) {
        if(word == "") return true;
        if(matrix.size() == 0) return false;
        int n = matrix.size();
        int m = matrix[0].size();
        // 定义标记访问数组
        vector<vector<bool> > visited(n, vector<bool>(m, false));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(matrix[i][j] == word[0]){
                    if(hasPath2(matrix, word, visited, i, j, 0)){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    bool hasPath2(vector<vector<char> >& matrix, string word, vector<vector<bool> >& visited, int i, int j, int k) {
         // 剪枝，排除一些非法情况，或者该位置已经被访问过
         if(i<0 || j<0 || i>=matrix.size() || j>=matrix[0].size() || visited[i][j]==true) return false;
         // 字符已经遍历到最后且匹配时，表示存在
         if(k == word.length()-1 && matrix[i][j] == word[k]) return true;
         if(word[k] == matrix[i][j]){
             // 只有相等才会继续比较
             visited[i][j] = true;
             // 向上下左右四个方向进行dfs
             if(hasPath2(matrix, word, visited, i+1, j, k+1)
             || hasPath2(matrix, word, visited, i-1, j, k+1)
             || hasPath2(matrix, word, visited, i, j+1, k+1)
             || hasPath2(matrix, word, visited, i, j-1, k+1)){
                 return true;
             }else{
                 // 都不满足则直接返回，需要把原来的复原
                 visited[i][j] = false;
                 return false;
             }
         }
         // 不相等直接返回
         return false;
     }

时间复杂度：与Java实现相同；
空间复杂度：与Java实现相同。