題目描述
請設計一個函式，用來判斷在一個矩陣中是否存在一條包含某字串所有字符的路徑，路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子，如果一條路徑經過了矩陣中的某一個格子，則該路徑不能再進入該格子，
例如
矩陣中包含一條字串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因為字串的第一個字符b占據了矩陣中的第一行第二個格子之后，路徑不能再次進入該格子，
思路
1、簡單記憶化搜索：每次搜索需要重新初始化vis陣列 2、回溯法：vis陣列無需重復重繪時間復雜度O(mn)，空間復雜度O(mn)，
代碼
簡單記憶化搜索
public class Solution {
int row;
int col;
private boolean[][] vis;
private boolean check(char[] mat, int x, int y, char[] str, int step) {
if(x < 0 || x >= row || y < 0 || y >= col) {
return false;
}
if(mat[x*col+y] == str[step] && !vis[x][y]) {
if(step + 1 == str.length) {
return true;
}
vis[x][y] = true;
return check(mat, x + 1, y, str, step + 1) ||
check(mat, x - 1, y, str, step + 1) ||
check(mat, x, y + 1, str, step + 1) ||
check(mat, x, y - 1, str, step + 1);
}
return false;
}
public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
if(matrix == null || matrix.length == 0 || rows < 1 || cols < 1 || str == null || str.length == 0) {
return false;
}
row = rows;
col = cols;
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
vis = new boolean[rows][cols];
if(check(matrix, i, j, str, 0)) {
return true;
}
}
}
return false;
}
}
回溯法
public class Solution {
int row;
int col;
private boolean[][] vis;
private boolean check(char[] mat, int x, int y, char[] str, int step) {
if(x < 0 || x >= row || y < 0 || y >= col || mat[x*col+y] != str[step] || vis[x][y]) {
return false;
}
if(step + 1 == str.length) {
return true;
}
vis[x][y] = true;
if(check(mat, x + 1, y, str, step + 1) ||
check(mat, x - 1, y, str, step + 1) ||
check(mat, x, y + 1, str, step + 1) ||
check(mat, x, y - 1, str, step + 1)) {
return true;
}
vis[x][y] = false;
return false;
}
public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
if(matrix == null || matrix.length == 0 || rows < 1 || cols < 1 || str == null || str.length == 0) {
return false;
}
row = rows;
col = cols;
vis = new boolean[rows][cols];
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
if(check(matrix, i, j, str, 0)) {
return true;
}
}
}
return false;
}
}
筆記
當記憶化陣列不可以重用時，考慮回溯，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/57205.html
標籤：其他
下一篇：主定理的數學證明