题解 | #矩阵中的路径#
矩阵中的路径
http://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param matrix char字符型vector<vector<>>
* @param word string字符串
* @return bool布尔型
*/
bool hasPath(vector<vector<char> >& matrix, string word) {
int row = matrix.size();
int col = matrix[0].size();
for(int i=0; i<row; i++){
for(int j=0; j<col; j++){
if(dfs(matrix, i, j, 0, word))
return true;
}
}
return false;
// write code here
}
bool dfs(vector<vector<char>>& matrix, int i, int j, int k, string word){
if(j>=matrix[0].size() || j<0 || i>=matrix.size() || i<0 || word[k]!= matrix[i][j])
return false;
if(k==word.size()-1)
return true;
matrix[i][j] = '\0';
bool res = dfs(matrix, i+1, j, k+1, word) || dfs(matrix, i-1, j, k+1, word)
|| dfs(matrix, i, j+1, k+1, word) || dfs(matrix, i, j-1, k+1, word);
matrix[i][j] = word[k];
return res;
}
};
时间复杂度 O(3^KMN)O(3
K
MN) ： 最差情况下，需要遍历矩阵中长度为 KK 字符串的所有方案，时间复杂度为 O(3^K)O(3
K
)；矩阵***有 MNMN 个起点，时间复杂度为 O(MN)O(MN) 。
方案数计算： 设字符串长度为 KK ，搜索中每个字符有上、下、左、右四个方向可以选择，舍弃回头（上个字符）的方向，剩下 33 种选择，因此方案数的复杂度为 O(3^K)O(3
K
) 。
空间复杂度 O(K)O(K) ： 搜索过程中的递归深度不超过 KK ，因此系统因函数调用累计使用的栈空间占用 O(K)O(K) （因为函数返回后，系统调用的栈空间会释放）。最坏情况下 K = MNK=MN ，递归深度为 MNMN ，此时系统栈使用 O(MN)O(MN) 的额外空间。
作者：jyd
链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/solution/mian-shi-ti-12-ju-zhen-zhong-de-lu-jing-shen-du-yo/
