题目链接

LeetCode
牛客网

题目描述

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

解题思路（回溯法+DFS+递归+剪枝）

使用回溯法（backtracking）进行求解，它是一种暴力搜索方法，通过搜索所有可能的结果来求解问题。回溯法在一次搜索结束时需要进行回溯（回退），将这一次搜索过程中设置的状态进行清除，从而开始一次新的搜索过程。例如下图示例中，从 f 开始，下一步有 4 种搜索可能，如果先搜索 b，需要将 b 标记为已经使用，防止重复使用。在这一次搜索结束之后，需要将 b 的已经使用状态清除，并搜索 c。
image.png

  • 深度优先搜索： 可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
  • 剪枝： 在搜索中，遇到 这条路不可能和目标字符串匹配成功 的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为 可行性剪枝 。

12. 矩阵中的路径 - 图3

dfs回溯过程

  1. dfs(){
  4.     // 第一步，检查下标
  7.     // 第二步：检查是否被访问过，或者是否满足当前匹配条件
  10.     // 第三步：检查是否满足返回结果条件
  13.     // 第四步：都没有返回，说明应该进行下一步递归
  14.     // 标记
  15.     dfs(下一次)
  16.     // 回溯
  17. }  
  18. int main() {
  19.     dfs(0, 0);
  20. }

DFS 解析：
  • 递归参数： 当前元素在矩阵 board 中的行列索引 i 和 j ，当前目标字符在 word 中的索引 k 。
  • 终止条件：
    1. 返回 false ： (1) 行或列索引越界 或 (2) 当前矩阵元素与目标字符不同 或 (3) 当前矩阵元素已访问过 （ (3) 可合并至 (2) ） 。
    2. 返回 true ： k = len(word) - 1 ，即字符串 word 已全部匹配。
  • 递推工作：
    1. 标记当前矩阵元素： 将 board[i][j] 修改为 空字符 '\0' ，代表此元素已访问过，防止之后搜索时重复访问。
    2. 搜索下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，使用 或 连接 （代表只需找到一条可行路径就直接返回，不再做后续 DFS ），并记录结果至 res 。
    3. 还原当前矩阵元素： 将 board[i][j] 元素还原至初始值，即 word[k] 。

  • 返回值： 返回布尔量 res ，代表是否搜索到目标字符串。

    1. class Solution {
    2. public:
    3.   bool exist(vector<vector<char>>& board, string word) {
    4.       rows = board.size();    // 行数
    5.       cols = board[0].size(); // 列数
    6.       for(int i = 0; i < rows; i++) {
    7.           for(int j = 0; j < cols; j++) {
    8.               if(dfs(board, word, i, j, 0)) return true;
    9.           }
    10.       }
    11.       return false;
    12.   }
    13. private:
    14.   int rows,cols;
    15.   bool dfs(vector<vector<char>>& board, string word,int i,int j,int k){
    16.       if(i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != word[k]) return false; // 越界或当前矩阵元素与目标字符不同或当前矩阵元素已访问过，则为false
    17.                                                                                            // 当前矩阵元素已访问过，标记当前矩阵元素： 将 board[i][j] 修改为'\0'
    18.                                                                                            // 所以判断条件和当前矩阵元素与目标字符不同一样
    19.       if(k == word.size() - 1) return true;   // k = len(word) - 1 ，即字符串 word 已全部匹配
    20.       board[i][j] = '\0';     // 当前矩阵元素已访问过，标记当前矩阵元素： 将 board[i][j] 修改为'\0'
    21.       bool res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || 
    22.                     dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);  // 搜索下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，
    23.                                                                                               // 使用 或 连接 （代表只需找到一条可行路径就直接返回)
    24.       board[i][j] = word[k];  // 还原当前矩阵元素： 将 board[i][j] 元素还原至初始值，即 word[k]
    25.       return res;
    26.   }
    27. };

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

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

**