題目：
給定一個二維網格和一個單詞，找出該單詞是否存在于網格中，
單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格，同一個單元格內的字母不允許被重復使用，
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
給定 word = "ABCCED", 回傳 true.
給定 word = "SEE", 回傳 true.
給定 word = "ABCB", 回傳 false.解題方法：遞回回溯
type pair struct{ x, y int }
var directions = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} // 上下左右
func exist(board [][]byte, word string) bool {
h, w := len(board), len(board[0])
//初始化二維陣列
vis := make([][]bool, h)
for i := range vis {
vis[i] = make([]bool, w)
}
var check func(i, j, k int) bool
check = func(i, j, k int) bool {
if board[i][j] != word[k] { // 剪枝：當前字符不匹配
return false
}
//k表示字串對應的下標數即長度
if k == len(word)-1 { // 單詞存在于網格中
return true
}
//已訪問設定為true
vis[i][j] = true
defer func() { vis[i][j] = false }() // 回溯時還原已訪問的單元格
for _, dir := range directions {
//重新確定下標并判斷下標的有效性和判斷下標是否訪問過
if newI, newJ := i+dir.x, j+dir.y; 0 <= newI && newI < h && 0 <= newJ && newJ < w && !vis[newI][newJ] {
if check(newI, newJ, k+1) {
return true
}
}
}
return false
}
for i, row := range board {
for j := range row {
if check(i, j, 0) {
return true
}
}
}
return false
}
遞回回溯的思想，先判斷單詞第一個字符的是否存在，然后上下左右進行遞回查找，每個位上亦是如此，如果發現字符不相等就直接return相當于剪枝操作，遞回要注意終止條件，當到下標達到與字串長度相等時，則結束遞回，
參考鏈接：https://leetcode-cn.com/problems/word-search/solution/dan-ci-sou-suo-by-leetcode-solution/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/172446.html
標籤：其他