79 单词搜索

题目描述#

给定一个 m x n 的二维字符网格 board 和一个字符串 word，判断 word 是否存在于网格中。

单词需要按顺序由相邻单元格中的字符组成，相邻只包含水平和垂直方向。同一个单元格在同一次搜索路径中不能被重复使用。

思路#

这题可以把每个格子都当作单词的起点，然后从这个起点开始做深度优先搜索。递归函数 dfs(i, j, l) 表示当前来到坐标 (i, j)，准备匹配 word[l] 这个字符。嘿嘿，就像在网格里按顺序找线索，每一步都只能往上下左右拍下一张“相邻照片”。

递归先处理几个边界：如果 l == len(word)，说明单词已经全部匹配完成，可以返回 true；如果坐标越界，直接返回 false；如果当前格子已经访问过，或者当前字符和 word[l] 不相等，也不能继续走。

为了避免同一个格子被重复使用，代码在进入某个格子后，先把 board[i][j] 临时改成 '#'，表示这个格子已经在当前路径中。然后枚举四个方向继续搜索下一位字符。搜索结束后，再把格子的原字符恢复回来，这就是回溯里的“恢复现场”。没错没错，走过的路要做标记，但离开时也要擦掉脚印，不然其他路线就被误伤啦。

外层循环会枚举每个格子作为起点，只要有任意一次搜索成功，就可以立刻返回 true。最坏情况下，每个格子都可能作为起点进行搜索，单词长度为 L，时间复杂度可以粗略看作 O(m * n * 4^L)；额外空间主要是递归栈，为 O(L)，不计原地标记使用的输入网格。

思维边界#

网格回溯：每个格子都可能是起点，需要从所有位置尝试 DFS。
方向数组：用四个方向表示水平和垂直相邻，不包含斜向移动。
原地标记：把访问过的格子临时改成 '#'，避免同一条路径重复使用。
恢复现场：递归搜索结束后必须还原字符，否则会影响其他起点或分支。
终止条件：当 l == len(word) 时，说明所有字符已经匹配成功。

代码#

func exist(board [][]byte, word string) bool {
	dp := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
	m := len(board)
	n := len(board[0])
	var dfs func(int, int, int) bool
	// i 为 x 轴坐标，j 为 y 轴坐标， l 为当前验证的长度
	dfs = func(i, j, l int) bool {
		if l == len(word) {
			return true
		}
		if i < 0 || i >= m || j < 0 || j >= n {
			return false
		}
		// 当前已经访问过 或者 当前访问的索引和word的对应的字母不一样
		if board[i][j] == '#' || board[i][j] != word[l] {
			return false
		}
		bank := board[i][j]
		board[i][j] = '#'
		ans := false
		for _, v := range dp {
			ans = ans || dfs(i+v[0], j+v[1], l+1)
		}
		board[i][j] = bank
		return ans
	}

	// DFS 深度优先搜索遍历
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if dfs(i, j, 0) {
				return true
			}
		}
	}
	return false
}