請設計一個函式，用來判斷在一個矩陣中是否存在一條包含某字串所有字符的路徑，路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子，如果一條路徑經過了矩陣中的某一個格子，則該路徑不能再進入該格子
解題思路
使用回溯思想：
-
根據給定陣列，初始化一個標志位陣列，初始化為 false，表示未走過，true 表示已經走過，不能走第二次
-
根據行數和列數，遍歷陣列，先找到一個與 str 字串的第一個元素相匹配的矩陣元素，進入 dfs
-
根據 i 和 j 先確定一維陣列的位置，因為給定的 matrix 是一個一維陣列
-
確定遞回終止條件：越界，當前找到的矩陣值不等于陣列對應位置的值，已經走過的，這三類情況，都直接 false，說明這條路不通
-
若 k 已經判斷到了最后一位，此時說明是匹配成功的
-
遞回尋找周圍四個格子是否符合條件，只要有一個格子符合條件，就繼續再找這個符合條件的格子的四周是否存在符合條件的格子，直到k到達末尾或者不滿足遞回條件就停止
-
走到這一步，說明本次是不成功的，我們要還原一下標志位陣列 index 處的標志位，進入下一輪的判斷
public class Solution {
public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
boolean[] flag = new boolean[matrix.length];
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
if(dfs(flag, i, j, rows, cols, matrix, str, 0)) {
return true;
}
}
}
return false;
}
public boolean dfs(boolean[] flag, int i, int j, int rows, int cols, char[] matrix, char[] str, int k) {
int index = cols * i + j;
if(i < 0 || j < 0 || i >= rows || j >= cols || flag[index] == true || matrix[index] != str[k]) {
return false;
}
if(k == str.length - 1) {
return true;
}
flag[index] = true;
if(dfs(flag, i + 1, j, rows, cols, matrix, str, k + 1) ||
dfs(flag, i - 1, j, rows, cols, matrix, str, k + 1) ||
dfs(flag, i, j + 1, rows, cols, matrix, str, k + 1) ||
dfs(flag, i, j - 1, rows, cols, matrix, str, k + 1)) {
return true;
}
flag[index] = false;
return false;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/244610.html
標籤：其他
上一篇：滑動視窗的最大值