《剑指offer》 12.矩阵中的路径

剑指offer
留言

note:典型的迷宫找路的问题，一般都是使用基于dfs+剪枝的回溯方法。

题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

image.png

示例 1：

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

1
2
输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false

提示：

  • 1 <= board.length <= 200
  • 1 <= board[i].length <= 200
  • board 和 word 仅由大小写英文字母组成

方法：回溯法

思路

很显然，对于这种矩阵搜索、迷宫找路径的题目，一般必然是使用深度优先搜索+剪枝来进行解决的。

在这道题中，我们首先可以想到，我们只需要以矩阵中每个元素作为起始元素，判断以这个元素开始是否能够找到word。

然后开始设想如何以某个元素作为起始进行寻找。首先考虑的深度优先搜索，就会发现搜索过的地方会重复搜索，浪费大量时间，甚至递归无法停止，所以我们一定要标记好访问过的地方，一但访问了，就要做好标记，而一但发现此路不通，进行回溯的时候，就要把标记改回来。这就是剪枝的部分。

考虑dfs的流程是如何的。一般dfs肯定是使用递归写方便，递归的终止条件非常重要，很显而易见的终止条件有以下几个

  • 超出矩阵边界。返回false。
  • 访问到的元素和要找的字符串中对应的元素不相同。返回false
  • 字符串所有字符都已经找遍，全部对应上了。完全匹配。返回true

那递归要完成什么呢？

  • 标记已经访问的元素
  • 向上下左右四个方向进行探索，看往下走是否满足字符串的匹配（开启下层递归），四个方向只要有一个方向可以满足就满足情况
  • 恢复已经访问的标记。

为什么之后要恢复已经访问的标记呢？这是因为走到这一步时，下层递归都已经完成，本层工作也已经做完，将要返回到上层递归，而所有的本层递归所做的标记，对于上层递归而言是无意义的。甚至会干扰的上层递归的访问。所以要恢复所做的标记。也就是说，标记仅影响本层以下的所有递归操作。

标记的行为可以有很多实现，比如重新建立一个等大的矩阵来记录。但是为了节省空间，我们不妨就在原数组进行更改，更改为一个不可能在字符串中出现的元素就好，然后在递归结束之后，再将元素改过来就可以了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    int row,col;

    bool dfs(vector<vector<char>> &board,string word,int i,int j,int k){
        if(i<0||i>=row||j<0||j>=col||board[i][j]!=word[k]){ // board[i][j]!word[k]一定要放在最后，避免数组越界错误
            return false;
        }
        if(k==word.size()-1)
            return true;
        board[i][j]='0';    // 更改赋值 进行剪枝
        bool res = dfs(board,word,i+1,j,k+1) || dfs(board,word,i-1,j,k+1) || dfs(board,word,i,j+1,k+1) || dfs(board,word,i,j-1,k+1);
        board[i][j] = word[k];  // 改回原值，回溯上层
        return res;
    }

public:
    bool exist(vector<vector<char>>& board, string word) {
        row = board.size();
        col = board[0].size();

        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(dfs(board,word,i,j,0))
                    return true;
            }
        }

        return false;
    }
};

复杂度分析

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

  • 时间复杂度 $O(3^KMN)$： 最差情况下，需要遍历矩阵中长度为$ K $字符串的所有方案，时间复杂度为 $O(3^K)$；矩阵中共有$ MN$个起点，时间复杂度为 $O(MN)$ 。

方案数计算： 设字符串长度为 $KK$ ，搜索中每个字符有上、下、左、右四个方向可以选择，舍弃回头（上个字符）的方向，剩下 3 种选择，因此方案数的复杂度为 $O(3^K)$ 。

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

    (复杂度分析参考题解)