题目描述
请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子,则之后不能再次进入这个格子。
注意:
输入的路径不为空;
所有出现的字符均为大写英文字母;
样例
matrix=
[
["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]
]
str="BCCE" , return "true"
str="ASAE" , return "false"
算法1
(暴力搜索)
时间复杂度
参考文献
JAVA 代码
class Solution {
char[][] matrix;
String str;
public boolean hasPath(char[][] matrix, String str) {
this.matrix = matrix;
this.str = str;
for(int i = 0; i < matrix.length; i++){
for (int j = 0; j < matrix[i].length; j++){
if (dfs(0, i, j)) return true;
}
}
return false;
}
public boolean dfs(int u, int x, int y){
if (str.charAt(u) != matrix[x][y]) return false;
if (u == str.length() - 1) return true;
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, -1, 0, 1};
char t = matrix[x][y];
matrix[x][y] = '*';
for (int i = 0; i < 4; i++){
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < matrix.length && b >= 0 && b < matrix[a].length){
if (dfs(u+1, a, b)) return true;
}
}
matrix[x][y] = t;
return false;
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla