溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關golang刷leetcode 技巧之如何解決矩陣中的路徑問題，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
請設計一個函數(shù)，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一格開始，每一步可以在矩陣中向左、右、上、下移動一格。如果一條路徑經過了矩陣的某一格，那么該路徑不能再次進入該格子。例如，在下面的3×4的矩陣中包含一條字符串“bfce”的路徑（路徑中的字母用加粗標出）。
[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]
但矩陣中不包含字符串“abfb”的路徑，因為字符串的第一個字符b占據(jù)了矩陣中的第一行第二個格子之后，路徑不能再次進入這個格子。
示例 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
解題思路
1，深度優(yōu)先遍歷
2，首字母不匹配可以剪枝
3，注意golang slice 數(shù)據(jù)地址一樣，所以，需要clone 路徑，否則會回溯失敗
測試用例
[["A","B","C","E"],["S","F","E","S"],["A","D","E","E"]]
"ABCESEEEFS"
[["a","b"]]
"ba"
[["a"]]
"a"
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
"ABCCED"
代碼實現(xiàn)
func exist(board [][]byte, word string) bool {for i:=0;i<len(board);i++{for j:=0;j<len(board[0]);j++{if board[i][j]!=word[0]{continue}mark:=getMark(board)if dfs(board,mark,i,j,word){return true}//fmt.Println(mark)}}return false}func dfs(board [][]byte,mark1 [][]int,i,j int,word string)bool{if word=="" {return true}if i<0 || i>=len(board) || j<0 || j>=len(board[0]) || board[i][j]!=word[0] || mark1[i][j]!=0{return false}if len(word)==1 && word[0]==board[i][j]{return true}mark:=cloneMark(mark1)mark[i][j]=1return dfs(board,mark,i+1,j,word[1:]) ||dfs(board,mark,i,j+1,word[1:]) ||dfs(board,mark,i-1,j,word[1:])||dfs(board,mark,i,j-1,word[1:])}func getMark(board [][]byte)[][]int{mark:=make([][]int,len(board))for k:=0;k<len(board);k++{mark[k]=make([]int,len(board[0]))}return mark}func cloneMark(mark [][]int)[][]int{mark1:=make([][]int,len(mark))for i:=0;i<len(mark);i++{mark1[i]=make([]int,len(mark[0]))for j:=0;j<len(mark[0]);j++{mark1[i][j]=mark[i][j]}}return mark1}
關于“golang刷leetcode 技巧之如何解決矩陣中的路徑問題”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。
免責聲明：本站發(fā)布的內容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經查實，將立刻刪除涉嫌侵權內容。
