📑 题目：79. 单词搜索

🚀 本题 LeetCode 传送门

题目大意

给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

解题思路

• 在地图上的任意一个起点开始，向 4 个方向分别 DFS 搜索，直到所有的单词字母都找到了就输出 true，否则输出 false。

代码

package leetcode
var dir = [][]int{
 []int{-1, 0},
 []int{0, 1},
 []int{1, 0},
 []int{0, -1},
}
func exist(board [][]byte, word string) bool {
 visited := make([][]bool, len(board))
 for i := 0; i < len(visited); i++ {
  visited[i] = make([]bool, len(board[0]))
 }
 for i, v := range board {
  for j := range v {
   if searchWord(board, visited, word, 0, i, j) {
    return true
   }
  }
 }
 return false
}
func isInBoard(board [][]byte, x, y int) bool {
 return x >= 0 && x < len(board) && y >= 0 && y < len(board[0])
}
func searchWord(board [][]byte, visited [][]bool, word string, index, x, 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 < 4; i++ {
   nx := x + dir[i][0]
   ny := y + dir[i][1]
   if isInBoard(board, nx, ny) && !visited[nx][ny] && searchWord(board, visited, word, index+1, nx, ny) {
    return true
   }
  }
  visited[x][y] = false
 }
 return false
}