题目描述
题目：79. 单词搜索
解题思路
遍历
首先找重复性，题目说给定单词是否存在于二维数组中，可以简化为从 (x, y) 走 n 步（n 表示单词长度），查看给定单词是否存在。然后再遍历二维数组里的所有点，看是否存在给定单词。
func exist(board [][]byte, word string) bool {
for x:=0;x<n;x++ {
for y:=0;y<m;y++ {
if dfs(x, y, 0) {
return true
}
}
}
return false
}
回溯
从 (x, y) 走 n 步，每一步都可以从上下左右四个方向“试探步”，直到走完 n 步，然后再比较“走过的路径” 和给定单词是否相等。
func backtrack(x int, y int, index int, s *[]byte) {
// 终止条件：走完 n 步
if index == len(word) {
return string(s) == word
}
if !visited[x][y] {
visited[x][y] = true
s = append(s, board[x][y])
for i:=0;i<direction;i++ {
newX, newY := x+direction[i][0], y+direction[i][1]
if backtrack(newX, newY, index+1) {
return true
}
}
s = s[:len(s)]
visited[x][y] = false
}
return false
}
此代码存在问题，没有考虑边界的问题，当向上下左右移动时，不能超过边界，因此代码调整为：
func backtrack(x int, y int, index int, s *[]byte) {
// 终止条件：走完 n 步
if index == len(word) {
return string(s) == word
}
if !visited[x][y] {
visited[x][y] = true
s = append(s, board[x][y])
for i:=0;i<direction;i++ {
newX, newY := x+direction[i][0], y+direction[i][1]
if inArea(newX, newY) && backtrack(newX, newY, index+1) {
return true
}
}
s = s[:len(s)]
visited[x][y] = false
}
return false
}
func inArea(x int, y int) bool {
return x < n && x >= 0 && y < m && y >= 0
}
剪枝
上面的代码可以进一步优化，在回溯过程中，可以预先判断结果，假如走到第 i 步时，此时的字符与给定单词的第 i 位字符不相等，则可以剪掉后续的比较，即剪掉分支。
注：回溯、dfs 本质上是递归，函数调用的过程会生成一颗递归树。
func backtrack(x int, y int, index int) bool {
if index == len(word)-1 {
return board[x][y] == word[index]
}
if board[x][y] == word[index] {
visited[x][y] = true
// 遍历四个方向
for i := 0; i < len(direction); i++ {
newX, newY := x+direction[i][0], y+direction[i][1]
if inArea(newX, newY) && !visited[newX][newY] {
if backtrack(newX, newY, index+1) {
return true
}
}
}
visited[x][y] = false
}
return false
}
func inArea(x int, y int) bool {
return x < n && x >= 0 && y < m && y >= 0
}
代码实现
var direction = [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
var visited [][]bool
var n, m int
func exist(board [][]byte, word string) bool {
n = len(board)
if n == 0 {
return false
}
m = len(board[0])
if m == 0 {
return false
}
visited = make([][]bool, n)
for i := 0; i < n; i++ {
visited[i] = make([]bool, m)
}
for x := 0; x < n; x++ {
for y := 0; y < m; y++ {
if backtrack(board, word, 0, x, y) {
return true
}
}
}
return false
}
func backtrack(board [][]byte, word string, index int, x int, y int) bool {
if index == len(word)-1 {
return board[x][y] == word[index]
}
if board[x][y] == word[index] {
visited[x][y] = true
// 遍历四个方向
for i := 0; i < len(direction); i++ {
newX, newY := x+direction[i][0], y+direction[i][1]
if inArea(newX, newY) && !visited[newX][newY] {
if backtrack(board, word, index+1, newX, newY) {
return true
}
}
}
visited[x][y] = false
}
return false
}
func inArea(x int, y int) bool {
return x < n && x >= 0 && y < m && y >= 0
}
复杂度分析：
- 时间复杂度：O(n * m * L)，其中 n, m, L 分别表示二维数组的行、列和给定单词的长度。
- 最好情况，遍历二维数组第一个元素，且走一次就找到。
- 最坏情况，要遍历到二维数组的最后一个元素，并且各个方向都走完后，没找到结果。
- 空间复杂度：O(n * m)，其中 n, m 分别表示二维数组的行、列。只需要一个二维数组记录是否访问过元素。
总结
- 对于类似排列、组合的问题，第一时间要想到可以使用dfs、回溯来解决。
- 一般来说，回溯和剪枝是一起使用的，在优化时间复杂度时，记得考虑剪枝。