题目

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

示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

给定 word = “ABCCED“, 返回 true
给定 word = “SEE“, 返回 true
给定 word = “ABCB“, 返回 false

提示：

board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200

1 <= word.length <= 10^3

方案一

class Solution:
  def exist(self, board: List[List[str]], word: str) -> bool:
      if not board or not board[0]:
          return False
      m, n = len(board), len(board[0])
      if not word:
          return True
      def dfs(start, index) -> bool:
          # start: 当前字母的坐标
          # index: 当前查找字母的索引
          # q([((i, j), value)]): 递归过程中会修改 board 的值表示已经访问过，该参数用来将 board 的值修改回去
          if index == len(word) - 1:
              return True
          for next_i, next_j in next_ij(start[0], start[1]):
              if board[next_i][next_j] == word[index+1] and board[next_i][next_j] != 0:
                  # 回溯过程中保存节点值
                  tmp = board[next_i][next_j]
                  board[next_i][next_j] = 0
                  if dfs((next_i, next_j), index+1):
                      return True
                  board[next_i][next_j] = tmp
          return False
      def next_ij(i, j):
          if i < m - 1:
              yield i + 1, j
          if j < n - 1:
              yield i, j + 1
          if i > 0:
              yield i - 1, j
          if j > 0:
              yield i, j - 1
      # 所有起始节点坐标
      starts = []
      for i in range(m):
          for j in range(n):
              if board[i][j] == word[0]:
                  starts.append((i, j))
      for start in starts:
          # 使用tmp保存已经遍历过的节点值，并将二维表中节点值置为0
          tmp = board[start[0]][start[1]]
          board[start[0]][start[1]] = 0
          if dfs(start, 0):
              return True
          board[start[0]][start[1]] = tmp
      return False

方案二（同样思路 leetcode写法）

class Solution:
  def exist(self, board: List[List[str]], word: str) -> bool:
      def dfs(i, j, word, count):
          if count == len(word):
              return True
          if board[i][j] == 1:
              return False
          val = board[i][j]
          board[i][j] = 1
          for (x,y) in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
              if x>=0 and y>=0 and x<m and y<n and board[x][y]==word[count]:
                  if dfs(x, y, word, count+1):
                      return True
          board[i][j] = val
          return False
      m,n = len(board),len(board[0])
      root = []
      for i in range(m):
          for j in range(n):
              if board[i][j]==word[0]:
                  root.append((i,j))
      for i,j in root:
          if dfs(i,j,word,1):
              return True
      return False

方案三（回溯）

```go func exist(board [][]byte, word string) bool { if word == “” {

  return true

} if len(board) == 0 || len(board[0]) == 0 {

  return false

}

var res bool for i := 0; i < len(board); i++ {

  for j := 0; j < len(board[0]); j++ {
      if board[i][j] == word[0] {
          if len(word) == 1 {
              return true
          }
          visited := map[[2]int]bool{
              {i, j}: true,
          }
          dfs(board, word, i, j, 1, visited, &res)
          if res {
              return true
          }
      }
  }

}

return false }

func dfs(board [][]byte, word string, i, j, current int, visited map[[2]int]bool, res bool) { if res { return } if current >= len(word) { return }

for _, ij := range around(i, j, len(board), len(board[0])) {
    if visited[ij] {
        continue
    }

    if word[current] == board[ij[0]][ij[1]] {
        // 终止条件
        if current == len(word)-1 {
            *res = true
        }

        visited[ij] = true
        dfs(board, word, ij[0], ij[1], current+1, visited, res)
        visited[ij] = false
    }
}

}

func around(i, j, m, n int) [][2]int { ret := [][2]int{}

for _, each := range [][2]int{
    {i-1, j},
    {i+1, j},
    {i, j-1},
    {i, j+1},
} {
    if 0 <= each[0] && each[0] < m && 0 <= each[1] && each[1] < n {
        ret = append(ret, each)
    }
}

return ret

}

<a name="qQgWe"></a>
# 方案四（回溯）
```python
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            '''
            i, j 表示第 i, j 坐标
            k 表示遍历到第 k 个字符
            '''
            if 0 <= i <= len(board) or 0 <= j <= len(board[0]) or board[i][j] != word[k]: return False
            if len(word) - 1 == k: return True

            # 当前节点已遍历
            ch = board[i][j]
            board[i][j] = ""
            res = dfs(i-1, j, k+1) or dfs(i+1, j, k+1) or dfs(i, j-1, k+1) or dfs(i, j+1, k+1)
            board[i][j] = ch
            return res

        for i in range(0, len(board)):
            for j in range(0, len(board[0])):
                if dfs(i, j, 0):
                    return True

        return False

原文

https://leetcode-cn.com/explore/interview/card/2020-top-interview-questions/287/backtracking/1287/
https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/solution/mian-shi-ti-12-ju-zhen-zhong-de-lu-jing-shen-du-yo/

算法（leetcode）

79. 单词搜索

题目

方案一

方案二（同样思路 leetcode写法）

方案三（回溯）

原文