题目

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出：true

解析

首先这道题是一个二维的数组进行回溯，而且返回结果只是判断true or false，那么完全就不需要之前题目那么复杂存路径，就用一个变量来判断是否存在即可，而且只要存在了，就直接一层层返回。
另外这道题相当于从二维数组的每个位置开始，进行dfs，为了方便可以都将边界条件写到dfs函数中来进行退出；同时标记不能重复走的位置也可以直接修改原数组再回溯后改回去，不用新开二维数组。

func exist(board [][]byte, word string) bool {// 这道题的结果是判断是否存在，用一个遍历来存，满足则直接返回found := falsem, n := len(board), len(board[0])var dfs func(i, j, k int)dfs = func(i, j, k int) {// 已经找到，直接返回if found {return}// 超出索引范围if i < 0 || j < 0 || i >= m || j >= n {return}// 之前走过这个位置了，不能再走if board[i][j] == '*' { // 也可以新起一个二维数组来存这个改动return}// 元素不相等if board[i][j] != word[k] { // 比较的递归中的某个字符return}// 走到这代表元素相等，再判断长度if k == len(word)-1 {found = truereturn}// 到这里表示还没找到，但是目前还是符合预期的，dfs四个方向继续找tmp := board[i][j]board[i][j] = '*'dfs(i-1, j, k+1)dfs(i+1, j, k+1)dfs(i, j-1, k+1)dfs(i, j+1, k+1)board[i][j] = tmp}for i := 0; i < m; i++ {for j := 0; j < n; j++ {dfs(i, j, 0)}}return found
}