LeetCode–矩陣中的路徑
博客說明
文章所涉及的資料來自互聯網整理和個人總結，意在于個人學習和經驗匯總，如有什么地方侵權，請聯系本人洗掉，謝謝！
介紹
劍指 Offer 12. 矩陣中的路徑
主站 79
題目
請設計一個函式，用來判斷在一個矩陣中是否存在一條包含某字串所有字符的路徑，路徑可以從矩陣中的任意一格開始，每一步可以在矩陣中向左、右、上、下移動一格，如果一條路徑經過了矩陣的某一格，那么該路徑不能再次進入該格子，例如，在下面的3×4的矩陣中包含一條字串“bfce”的路徑（路徑中的字母用加粗標出），
[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]
但矩陣中不包含字串“abfb”的路徑，因為字串的第一個字符b占據了矩陣中的第一行第二個格子之后，路徑不能再次進入這個格子，
示例 1：
輸入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
輸出：true
示例 2：
輸入：board = [["a","b"],["c","d"]], word = "abcd"
輸出：false
提示：
1 <= board.length <= 200
1 <= board[i].length <= 200
思路
作者：jyd
深度優先搜索（DFS）+ 剪枝
深度優先搜索： 可以理解為暴力法遍歷矩陣中所有字串可能性，DFS 通過遞回，先朝一個方向搜到底，再回溯至上個節點，沿另一個方向搜索，以此類推，
剪枝： 在搜索中，遇到 這條路不可能和目標字串匹配成功 的情況（例如：此矩陣元素和目標字符不同、此元素已被訪問），則應立即回傳，稱之為 可行性剪枝 ，
步驟
遞回引數：
當前元素在矩陣 board 中的行列索引 i 和 j ，當前目標字符在 word 中的索引 k ，
終止條件：
回傳 falsefalse ： ① 行或列索引越界 或 ② 當前矩陣元素與目標字符不同 或 ③ 當前矩陣元素已訪問過 （③ 可合并至 ② ） ，
回傳 truetrue ： 字串 word 已全部匹配，即 k = len(word) - 1 ，
遞推作業：
-
標記當前矩陣元素： 將 board[i][j] 值暫存于變數 tmp ，并修改為字符 '/' ，代表此元素已訪問過，防止之后搜索時重復訪問，
-
搜索下一單元格： 朝當前元素的 上、下、左、右 四個方向開啟下層遞回，使用 或 連接 （代表只需一條可行路徑） ，并記錄結果至 res ，
-
還原當前矩陣元素： 將 tmp 暫存值還原至 board[i][j] 元素，
回溯回傳值：
回傳 res ，代表是否搜索到目標字串，
代碼
class Solution {
public boolean exist(char[][] board, String word) {
char[] words = word.toCharArray();
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
if(dfs(board,words,i,j,0)){
return true;
}
}
}
return false;
}
boolean dfs(char[][] board, char[] word, int i, int j, int k){
if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]){
return false;
}
if(k == word.length - 1){
return true;
}
char tmp = board[i][j];
board[i][j] = '/';
boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
board[i][j] = tmp;
return res;
}
}
感謝
Leetcode
以及勤勞的自己，個人博客，GitHub
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/17423.html
標籤：Java
上一篇：SpringCloud Alibaba Nacos 服務發現 Feign進行消費
下一篇：LeetCode–表示數值的字串