一天一道力扣Hot100（38）：深度优先算法---单词搜索

LeetCode 79. 单词搜索

个人主页：
> 我不会起名字322 < （欢迎各位大佬莅临😊）

其他栏目：
> 技术栈学习笔记 <

其他栏目：
> 力扣Hot100题目解析 <

其他栏目：
> Go项目学习笔记 <

前言：

上一篇括号生成里，我们再次用回溯的"三要素"——路径、选择列表、结束条件——把一道看起来和组合总和完全不同的题给套了进去。当时我说：题目变了，形式变了，但三要素的骨架没变。

今天这道单词搜索，是对这句话的又一次检验，而且是更狠的一次——它连"一维数组"都不是了，直接把战场搬到了二维网格上。选择列表不再是一个数组、也不是两个计数器，而是当前位置的上下左右四个邻居。但你别慌，我们一起来看看，三要素在这道题里分别变成了什么。

整体的一个模板还是这样的：

func backtrack(路径, 选择列表) {
if 满足结束条件 {
结果集 = append(结果集, 路径的拷贝)
return
}
for 选择 := 选择列表 {
做选择 // 路径加入该选择
backtrack(路径, 新的选择列表)
撤销选择 // 路径移除该选择
}
}

下面我们来看一道题目深入理解一下

给定一个 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 仅由大小写英文字母组成

搜索的规则

在动手写代码之前，先想清楚"一次合法的搜索"到底要满足什么。有三个约束缺一不可：

第 3 条尤其关键。比如示例 3 的 "ABCB"，走完 A→B→C 之后想再走回 B，但那个 B 已经被用过了，所以不合法。这个约束直接决定了我们要引入一个 used 数组——或者，更巧妙地，直接在 board 上原地修改来标记（这是后话）。

• 首先，我们不需要排序，也不需要一维数组。这道题的输入是一个二维字符网格 board 和一个字符串 word，没有候选数组，所以组合总和里的 sort.Ints 和 startIndex 在这里都用不上。这正说明：三要素是本质，具体形式随题目而变。

• 其次，我们要定义几个数据

• 一个是当前匹配到 word 的第几个字符（路径）

  index int // 表示 path 已经匹配到 word[index]

  注意：这里不像括号生成那样传一个 path []byte，因为 word 本身就是要匹配的"目标路径"，我们只需要一个下标来记录进度即可。

• 一个是结果标志位，用来记录是否已经找到

  found := false

  因为这道题只要求返回 true / false，不需要收集所有解，所以用一个布尔值就够了。

• 上面两个是确定的，最后一个看题目不同来自己确定。这道题我们需要记录哪些格子已经被用过，用来避免重复访问

  used := make([][]bool, m)
  for i := range used {
  used[i] = make([]bool, n)
  }

  注意：这里不像括号生成那样传 open, close 两个计数器，因为括号题统计的是"数量"，而单词搜索要防的是"同一个格子被重复踩"。

• 还有一个方向数组，这是网格类题目的固定套路，把上下左右四个方向写死：

  dirs := [4][2]int{{–1, 0}, {1, 0}, {0, –1}, {0, 1}}

• 有了上面的数据，我们现在来套用模板来写这道题目

  func backtrack(路径, 选择列表) {
  首先是这个大框架，路径肯定要传 index，选择列表呢？
  这道题的选择列表不是数组，而是由 (i, j) 和 used 动态决定的：
  – 四个邻居中，在网格内 + 字符等于 word[index] + 未被 used 的，才是可选项
  }

  if 满足结束条件 {
  这里的满足条件就是 index == len(word)

  这里的"路径拷贝"其实就是把 found 置为 true —— 因为我们不需要真的把路径写出来，
  只要走到了底，就说明整条路径和 word 完全对上了
  found = true
  return
  }
  //这里我们要想，如果还能往下走怎么办呢？显然，继续下面的递归即可
  //那如果四个方向都走不通呢？那就自然返回，让上一层去尝试别的方向

  // 遍历四个方向（选择列表）
  for _, d := range dirs {
  ni, nj := i+d[0], j+d[1]
  // 越界 或者 字符不对 或者 已经用过，就跳过（这就是剪枝）
  if ni < 0 || ni >= m || nj < 0 || nj >= n ||
  board[ni][nj] != word[index] || used[ni][nj] {
  continue
  }

  used[ni][nj] = true // 做选择
  backtrack(ni, nj, index+1) // 递归
  used[ni][nj] = false // 撤销选择
  }

  注意一个细节：这道题和前面几道不一样——递归的入口不是"某个固定起点"，而是"任意一个等于 word[0] 的格子"。所以最外层要套一个双重循环：

  for i := 0; i < m; i++ {
  for j := 0; j < n; j++ {
  if board[i][j] == word[0] {
  // 从 (i, j) 出发搜索
  used[i][j] = true
  backtrack(i, j, 1)
  used[i][j] = false
  }
  }
  }

  只要中途 found 变成了 true，就可以直接返回 true，不用继续搜了——这就是"只找一条解"和"收集所有解"的区别。

• 因此，我们最后改造的函数就是

  func exist(board [][]byte, word string) bool {
  m, n := len(board), len(board[0])
  used := make([][]bool, m)
  for i := range used {
  used[i] = make([]bool, n)
  }
  found := false
  dirs := [4][2]int{{–1, 0}, {1, 0}, {0, –1}, {0, 1}}

  var backtrack func(i, j, index int)
  backtrack = func(i, j, index int) {
  // 结束条件：整个单词都匹配完了
  if index == len(word) {
  found = true
  return
  }

  // 遍历四个方向（选择列表）
  for _, d := range dirs {
  ni, nj := i+d[0], j+d[1]
  // 越界 或者 字符不对 或者 已经用过，就跳过（这就是剪枝）
  if ni < 0 || ni >= m || nj < 0 || nj >= n ||
  board[ni][nj] != word[index] || used[ni][nj] {
  continue
  }

  used[ni][nj] = true // 做选择
  backtrack(ni, nj, index+1) // 递归
  used[ni][nj] = false // 撤销选择

  // 已经找到就直接退出，不用继续搜了
  if found {
  return
  }
  }
  }

  // 枚举所有可能的起点
  for i := 0; i < m; i++ {
  for j := 0; j < n; j++ {
  if board[i][j] == word[0] {
  used[i][j] = true
  backtrack(i, j, 1)
  used[i][j] = false
  if found {
  return true
  }
  }
  }
  }
  return false
  }

• 进阶：能不能省掉 used 数组？

  可以。仔细观察会发现，used 数组的唯一作用就是"防止走回头路"。但我们完全可以在原地修改 board：进去的时候把 board[i][j] 改成一个不可能出现在 word 里的字符（比如 '#'），出来的时候再改回去。

  func exist(board [][]byte, word string) bool {
  m, n := len(board), len(board[0])
  dirs := [4][2]int{{–1, 0}, {1, 0}, {0, –1}, {0, 1}}

  var dfs func(i, j, index int) bool
  dfs = func(i, j, index int) bool {
  // 结束条件：整个单词都匹配完了
  if index == len(word) {
  return true
  }
  // 越界 或者 字符不对，就跳过
  if i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[index] {
  return false
  }

  tmp := board[i][j]
  board[i][j] = '#' // 做选择：标记已访问

  for _, d := range dirs {
  if dfs(i+d[0], j+d[1], index+1) {
  return true
  }
  }

  board[i][j] = tmp // 撤销选择：恢复现场
  return false
  }

  for i := 0; i < m; i++ {
  for j := 0; j < n; j++ {
  if dfs(i, j, 0) {
  return true
  }
  }
  }
  return false
  }

  这份代码比上一份更短、更省空间，而且把"做选择 / 撤销选择"直接体现在 board 的修改和恢复上——这就是回溯三要素最纯粹的样子。尤其注意 board[i][j] = '#' 和 board[i][j] = tmp 这一对操作，它们就是标准的"做选择 / 撤销选择"。

复杂度分析

• 时间复杂度：O(m × n × 3^L)，其中 L = len(word)。最坏情况下每个起点都要搜一遍，每次从 4 个方向里选一个方向继续（因为不能走回头路，所以实际分支约 3 个），深度为 L。
• 空间复杂度：O(L)，递归栈深度（不算输入输出）。原地修改版本不需要额外的 used 数组。

总结

回过头看，这道题再次印证了"回溯三要素"：

和前面几道题对比一下，区别一目了然：

题目变了，形式变了，但三要素的骨架没变。这就是为什么我说"想清楚这三样，剩下的就是套模板"。

本文是 《算法题目解析系列》 的第 [38] 篇，本系列将持续更新，每篇都提供清晰的思路与编程语言实现。欢迎关注，第一时间获取更新。如果你有想看的题目，也可以在评论区留言告诉我。