思路

题中给到的信息：

  • 上下左右随便移动，找到字符串路径
  • 访问可以重复，但是作为路径不能有重复

方法一：递归深度优先搜索

我们需要判断这个矩阵中的每一个结点是否可以走一条路径，即找到每个结点为起点，后续结点是否可以走出字符串字串的路径，该子问题又可以作为一个递归。因此，可以用图的递归dfs来解决。同时，在走的过程中，要设置一个和矩阵大小相同的bool矩阵表示是否已经访问，如果某个结点访问了，在同一条路线上就不能再访问了，其他路线依旧可以访问，所以若是某条路线不达标，记得将其改回来。 图片说明

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;
        }
        if(k == word.length() - 1){ //k为记录当前第几个字符
            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(word == "")  //优先处理特殊情况
            return true;
        if(matrix.size() == 0)
            return false;
        int n = matrix.size();
        int m = matrix[0].size();
        vector<vector<bool> > flag(n, vector<bool>(m, false)); //初始化flag矩阵记录是否走过
        for(int i = 0; i < n; i++){  //遍历矩阵找起点
            for(int j = 0; j < m; j++){
                if(dfs(matrix, n, m, i, j, word, 0, flag)){
                    return true;
                }
            }
        }
        return false;
    }
};

复杂度分析：

  • 时间复杂度：O(mn*k^3)，其中m与n为矩阵的边长，k为字符串的长度
  • 空间复杂度：O(mn)，辅助二位数组记录是否走过某节点

方法二：非递归深度优先搜索

具体做法：

像二叉树中序遍历一样，用栈来存储后面可能访问的结点，这里不适用flag数组标记而是直接替换矩阵中的值，当矩阵中的值被替换后代表已经路过，不能再去。回溯的时候也需要用栈记录前一个结点的下标，将替换后的字符再换回去即可回溯。

class Solution {
public:
    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();
        stack<pair<int, int>> s, deepnote;   //一个记录深度搜索的结点，一个记录回溯的时候前一个结点
        int index = 0;   //字符的序列
        for(int i = 0; i < n; i++)  //遍历每一个结点寻找头结点
            for(int j = 0; j < m; j++)
                s.push(make_pair(i, j));
        while(!s.empty()){
            int x=s.top().first;
            int y = s.top().second;
            if(x < 0 || x > n - 1 || y < 0 || y > m - 1){
                s.pop();
            }
            else if(matrix[x][y] == word[index] && matrix[x][y] != '/'){
                if(index == word.size() - 1)
                    return true;
                matrix[x][y]='/'; //将访问过的点标记
                index++;
                deepnote.push(make_pair(x, y)); //记录前一个结点
                s.push(make_pair(x, y + 1));  //将要访问的下一个结点入栈
                s.push(make_pair(x, y - 1));
                s.push(make_pair(x + 1, y));
                s.push(make_pair(x - 1, y));
            }else{
                if(!deepnote.empty() && deepnote.top() == s.top()){
                    index--;
                    matrix[x][y]=word[index]; //回溯
                    deepnote.pop();
                    s.pop();
                }
                else s.pop();
            }
        }
        return false;
    }
};

复杂度分析：

  • 时间复杂度：O(mn*k^3)，其中m与n为矩阵的边长，k为字符串的长度
  • 空间复杂度：O(mn)，dfs的栈最大是整个矩阵的大小