剑指 Offer 12. 矩阵中的路径
2022-03-14 本文已影响0人
邦_
func exist(_ board: [[Character]], _ word: String) -> Bool {
let wordArray = Array(word)
var tempArray = board
for i in 0...tempArray.count - 1 {
for j in 0...tempArray[0].count - 1 {
if dfs(&tempArray, wordArray, i, j, 0) {
return true
}
}
}
return false
}
func dfs(_ array: inout [[Character]],_ words:[Character],_ i:Int,_ j:Int,_ k: Int) -> Bool {
if i >= array.count || j >= array[0].count || i < 0 || j < 0 || array[i][j] != words[k]{
return false
}
if k == words.count - 1 {
return true
}
array[i][j] = "\0"
let res = dfs(&array, words, i + 1, j, k + 1) || dfs(&array, words, i - 1, j ,k + 1) || dfs(&array, words, i, j + 1, k + 1) || dfs(&array, words, i, j - 1, k + 1)
array[i][j] = words[k]
return res
}
