golang刷leetcode技巧之如何解決矩陣中的路徑問題

這篇文章將為大家詳細(xì)講解有關(guān)golang刷leetcode 技巧之如何解決矩陣中的路徑問題，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

創(chuàng)新互聯(lián)服務(wù)項目包括偏關(guān)網(wǎng)站建設(shè)、偏關(guān)網(wǎng)站制作、偏關(guān)網(wǎng)頁制作以及偏關(guān)網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，偏關(guān)網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到偏關(guān)省份的部分城市，未來相信會繼續(xù)擴大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

請設(shè)計一個函數(shù)，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一格開始，每一步可以在矩陣中向左、右、上、下移動一格。如果一條路徑經(jīng)過了矩陣的某一格，那么該路徑不能再次進(jìn)入該格子。例如，在下面的3×4的矩陣中包含一條字符串“bfce”的路徑（路徑中的字母用加粗標(biāo)出）。

[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]

但矩陣中不包含字符串“abfb”的路徑，因為字符串的第一個字符b占據(jù)了矩陣中的第一行第二個格子之后，路徑不能再次進(jìn)入這個格子。

示例 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]=1    return 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}

關(guān)于“golang刷leetcode 技巧之如何解決矩陣中的路徑問題”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學(xué)到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。

分享名稱：golang刷leetcode技巧之如何解決矩陣中的路徑問題
瀏覽路徑：http://muchs.cn/article20/pihijo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)建站、標(biāo)簽優(yōu)化、網(wǎng)站收錄、動態(tài)網(wǎng)站、、微信小程序

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)