题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。

路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。

如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。

注意：

• 输入的路径不为空；
• 所有出现的字符均为大写英文字母；

样例

matrix=
[
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]

str="BCCE" , return "true" 

str="ASAE" , return "false"

算法

(DFS) $O(n^2*3^k)$

先枚举每个单词的起点，然后枚举单词的每个字母进行匹配
在递归的过程中需要将已经用过的单词改成一个特殊字符，避免重复使用
注意最后回溯

时间复杂度

最坏情况下，枚举矩阵中的每个位置，总共 $n^2$ 个，每个位置都需要判断四个方向是否走得通，因为不能走回头路，所以最多判断三个方向，最坏情况下每次判断到最后一个位置发现不匹配，然后切换起始位置重新匹配，所以最坏情况下时间复杂度为 $O(n^2*3^k)$，k 为字符串的长度

C++ 代码

class Solution {
public:
    int n, m;

    bool hasPath(vector<vector<char>>& matrix, string &str) {
        if (matrix.empty()) return false;

        n = matrix.size(), m = matrix[0].size();
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (dfs(matrix, str, i, j, 0)) return true;
        return false;
    }

    bool dfs(vector<vector<char>>& matrix, string &str, int i, int j, int u)
    {
        if (str[u] != matrix[i][j]) return false;
        if (u == str.size() - 1) return true;

        int t = matrix[i][j];
        matrix[i][j] = '*';

        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        for (int k = 0; k < 4; k ++ )
        {
            int a = i + dx[k], b = j + dy[k];
            if (a >= 0 && a < n && b >= 0 && b < m)
            {
                if (dfs(matrix, str, a, b, u + 1)) return true;
            }
        }

        matrix[i][j] = t;
        return false;
    }
};