LeetCode 79 单词搜索 [Swift]
2019-11-28
题目
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
[‘A’,’B’,’C’,’E’],
[‘S’,’F’,’C’,’S’],
[‘A’,’D’,’E’,’E’]
]
给定 word = “ABCCED”, 返回 true.
给定 word = “SEE”, 返回 true.
给定 word = “ABCB”, 返回 false.
思路
本题主要采用 ”DFS“ 和 ”回溯“ 思想进行解题，针对本地，深度优先搜索很容易想到。
整体思路是遍历二维网格每个元素，分别为起始点开始回溯：加入第一个元素，如果符合要求，继续测试下一个元素，如果第一个元素的所有子元素都不符合要求，需要回退到第一个元素的前一个元素重复上述过程。
回溯算法的逻辑实现起来相对比较绕，对照代码，我们可以关注 backtrack 、validateFirst 、validateNext 这三个函数是如何对回溯逻辑进行拆解的，另外关于 状态回退，也是本题需要关注的一个点，注意 marked[r][c] = false 这行即执行的回退逻辑，我们可以看到本题的解决回退的代价是比较小的。
从本题中，我们还可以总结出回溯算法的基本套路：
首先需要实现一个 backtrack 函数。
在这个函数中，首先尝试一个元素 A 是否符合约束要求，如果不符合，返回 A 不符合要求；如果符合要求，对全局状态进行修改，代表将 A 置于 目标链 （完整的目标链即为回溯类算法题的解）中，此过程即为 validateFirst。
紧接着，对 A 的下一级元素 B 进行检验，递归的调用 backtrack 函数，此过程即为 validateNext，注意，如果 validateNext , 需要对全局状态进行回退，还记得全局状态是在哪步修改的么？请回顾 validateFirst 的过程找到它！
class Solution {
let direction : [[Int]] = [[-1, 0], [0, -1], [0, 1], [1, 0]]
var marked = [[Bool]]()
var board = [[Character]]()
var row : Int = 0
var col : Int = 0
var word : String = ""
func exist(_ board: [[Character]], _ word: String) -> Bool {
row = board.count
if row == 0 {
return false
}
col = board[0].count
marked = Array(repeating: Array(repeating: false, count: col), count: row)
self.word = word
self.board = board
for i in 0..<row {
for j in 0..<col {
if backtrack(i, j, 0) {
return true
}
}
}
return false
}
func backtrack(_ r : Int, _ c : Int, _ index : Int) -> Bool{
if !validateFirst(r, c, index) {
return false
}
if !validateNext(r, c, index) {
marked[r][c] = false
} else {
return true
}
return false
}
func validateFirst(_ r : Int, _ c : Int, _ index : Int) -> Bool {
let strChar = Character(word.subString(index, 1))
let boradChar = board[r][c]
if strChar == boradChar {
marked[r][c] = true
}
return marked[r][c]
}
func validateNext(_ r : Int, _ c : Int, _ index : Int) -> Bool {
if (index == word.count - 1) {
return true
}
for d in 0..<4 {
let newR = r + direction[d][0]
let newC = c + direction[d][1]
if inArea(newR, newC) && !marked[newR][newC] {
if backtrack(newR, newC, index + 1) {
return true
}
}
}
return false
}
func inArea(_ r : Int, _ c : Int) -> Bool {
return r >= 0 && r < row && c >= 0 && c < col
}
}
extension String {
func subString(_ start : Int, _ length : Int = -1) -> String {
var len = length
if len == -1 {
len = self.count - start
}
let st = self.index(startIndex, offsetBy:start)
let en = self.index(st, offsetBy:len)
return String(self[st ..< en])
}
}
回溯算法通常与 DFS ，减枝 结合进行解题，如果攻克下本题后，觉得意犹未尽，接下来可以挑战一下下面的题目 : )