题目链接

https://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6?tpId=13&&tqId=11218&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
###题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
[[“a”,“b”,”c”,”e”],
[“s”,“f”,“c”,”s”],
[“a”,”d”,”e”,“e”]]
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

方法一:深度优先遍历 + 回溯 + 剪枝

对于这类棋盘为背景的题目，这是经典的介绍深搜回溯法思想的题目,而解决此类问题有一个大致的模板

  • 棋盘中方向的表示:通过位移偏移量模拟每一次东西南北的移动
  • 恢复现场:当前搜索状态不满足要求回溯时，应该还原棋盘状态

思路分析

首先需要明确搜索是一种暴力求解的方式，只能应对一些棋盘规格较小且状态转移较为简单的题型，若问题规模比较大则不适用，因为通常耗费的时间与空间会比较大

  • 首先寻找搜索的起始点 （即棋盘与str[0]对应的）的位置 ,同时维护一个同样规格的棋盘 用于记录每个位置是否访问，保证每个位置只能被访问一次
  • 对当前搜索的位置进行上下左右一个单位的位移，同时判断新的位置是否合法，合法性的判断包括:1.新的位置不嫩越界， 2.新的位置的字符必须与对应的str的字符相同
  • 若当前状态满足则继续搜索，直到将str的每个字符都对应，若中途遇到不合法的情况则回溯，同时恢复现场

下面通过一个样例的图示分析搜索的过程
假设样例为:
[[“a”,“b”,”c”,”e”],
[“s”,“f”,“c”,”s”],
[“a”,”d”,”e”,“e”]]
str为：abcced
如图

  • 初始找dfs入口,同时枚举四个方向，找到合法的方向进行下一次搜索的状态转移，由图可以看到，向左与向上偏移会发生越界，故此类情况需要剪枝，而向下与向右中只有向右之后的位置对应的字符才会等于当前str位置的下一个字符，故搜索会向右进行，如图2
    图1
  • 当搜索位置到达图二位置时，依旧同上枚举四个偏移量，排除向上的越界情况，此时同时需要注意的是题目要求每个位置只能走一遍，故需要记录棋盘已经走过的位置，因为刚刚走过(0, 0)位置，故这个位置也要被排除，若之后发生回溯，则需要将标记已经走过的位置恢复现场处理即可。
  • 如此反复，直到遍历完str的最后一个元素即为搜索的出口，然后将结果返回即可，之后的搜索过程这里不再赘述
    图2

代码及注释如下

class Solution {
public:
    int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};  //四个偏移量
    int xlen, ylen;
    bool dfs(vector<vector<char>> &g, string &str, int u, int x, int y) {
        if (g[x][y] != str[u]) return false; //判断当前位置与str的字符是否对应
        if (u == str.size() - 1) return true; //搜索出口:str的所有字符都完成对应
        char t = g[x][y];
        g[x][y] = '*';   //记录已经走过的格子
        for (int i = 0; i < 4; i ++ ) {
            int X = x + dx[i], Y = y + dy[i];
            if (X >= 0 && X < xlen && Y >= 0 && Y < ylen) {  //判断转移的位置是否越出棋盘
                if (dfs(g, str, u + 1, X, Y)) return true;
            }
        }
        g[x][y] = t;  //恢复现场
        return false;
    }

    bool hasPath(vector<vector<char>>& matrix, string str) {
        xlen = matrix.size(), ylen = matrix[0].size();
        for (int i = 0; i < xlen; i ++ )
            for (int j = 0; j < ylen; j ++ )
                if (dfs(matrix, str, 0, i, j))
                    return true;
        return false;
    }


};

时间复杂度:因为最坏的情况即为将棋盘的每个位置都遍历一遍，而每个位置除首字母外都不能走已经走过的位置，故四个方向只有三个方向可以选择，故时间复杂度为O(mn*k^3), m * n即为棋盘位置数量
空间复杂度:O(n),即为字符串的长度