给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false提示：
- m == board.length
- n = board[i].length
- 1 <= m, n <= 6
- 1 <= word.length <= 15
- board 和 word 仅由大小写英文字母组成
进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
解题：
func exist(board [][]byte, word string) bool {
b := make([][]bool, len(board))
for i, v := range board {
b[i] = make([]bool, len(v))
}
l, m, n := len(word), len(board), len(board[0])
var search func(i, j, k int) bool
search = func(i, j, k int) bool {
if board[i][j] == word[k] {
if k+1 == l {
return true
}
b[i][j] = true
if i-1 >= 0 && !b[i-1][j] && search(i-1, j, k+1) {
return true
}
if i+1 < m && !b[i+1][j] && search(i+1, j, k+1) {
return true
}
if j-1 >= 0 && !b[i][j-1] && search(i, j-1, k+1) {
return true
}
if j+1 < n && !b[i][j+1] && search(i, j+1, k+1) {
return true
}
}
b[i][j] = false
return false
}
for i, v := range board {
for j, vv := range v {
if vv == word[0] && search(i, j, 0) {
return true
}
}
}
return false
}官方解答：
1.回溯
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
}
if k == len(word)-1 { // 单词存在于网格中
return 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
}