LeetCode 79. 单词搜索
题目描述
给定一个m x n的二维字符网格board和一个字符串word。
如果word存在于网格中，返回true；否则返回false。
单词必须按照字母顺序，通过相邻单元格中的字母构成。相邻单元格指水平相邻或垂直相邻的格子。
同一个单元格内的字母不允许被重复使用。
例如：
输入： board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] word = "ABCCED" 输出：true初始思路
这道题第一眼可以想到 DFS。
从某个格子出发，如果当前字符能匹配word中的某一位，就继续向上下左右四个方向搜索下一个字符。
也就是：
当前位置匹配 word[k] 然后去相邻位置匹配 word[k + 1]不过这里有两个关键限制：
1. 单词不一定从 board[0][0] 开始 2. 同一个格子在同一条路径里不能重复使用这两个点如果漏掉，DFS 的方向虽然对，但结果会出错。
解题思路
定义 DFS 函数：
dfs(i, j, k)含义是：
当前格子 board[i][j] 要匹配 word[k]所以进入 DFS 后，第一步就是判断当前格子是否匹配当前字符：
如果 board[i][j] != word[k]，说明这条路径不成立，直接返回如果当前字符已经是最后一个字符：
k == word.length - 1并且当前格子已经匹配成功，那么说明整个单词已经找到，可以返回true。
接下来需要处理访问标记。
因为同一个格子不能在同一条路径中重复使用，所以当前格子匹配成功后，要先标记为已经访问：
visited[i][j] = true然后枚举上下左右四个方向。如果下一个位置没有越界，并且没有在当前路径中被访问过，就继续递归搜索。
四个方向都搜索完之后，要恢复当前格子的访问状态：
visited[i][j] = false这就是典型的回溯：
做选择 递归搜索 撤销选择代码实现
class Solution { int[][] D = new int[][] { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; int m; int n; boolean ans; public boolean exist(char[][] board, String word) { m = board.length; n = board[0].length; ans = false; char[] w = word.toCharArray(); boolean[][] flag = new boolean[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == w[0]) { dfs(i, j, 0, board, w, flag); } } } return ans; } public void dfs(int i, int j, int k, char[][] board, char[] word, boolean[][] flag) { if (ans) return; if (board[i][j] != word[k]) { return; } if (k == word.length - 1) { ans = true; return; } flag[i][j] = true; for (int[] d : D) { int x = i + d[0]; int y = j + d[1]; if (x >= 0 && x < m && y >= 0 && y < n && !flag[x][y]) { dfs(x, y, k + 1, board, word, flag); } } flag[i][j] = false; } }为什么这样写
这题的搜索不是从固定位置开始，而是从任意格子开始。
所以外层必须枚举整个网格：
for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == w[0]) { dfs(i, j, 0, board, w, flag); } } }如果只从(0,0)开始，就会漏掉这种情况：
board = [ ['A','B'], ['C','D'] ] word = "CD"答案应该是true，因为可以从C开始搜索。
flag的作用是记录当前路径中已经使用过的格子。
比如：
board = [['A','B']] word = "ABA"如果不加访问标记，路径可能会变成：
A -> B -> A但这个A是同一个格子，被重复使用了，不符合题意。
所以递归进入当前格子后，要标记：
flag[i][j] = true;递归结束后，要恢复：
flag[i][j] = false;恢复的原因是：当前路径搜索完之后，其他路径仍然可以重新使用这个格子。
易错点
1. 只从(0,0)开始搜索
错误思路是直接写：
dfs(0, 0, 0, board, word);这样默认单词一定从左上角开始，会漏掉很多合法答案。
正确做法是枚举每个格子作为起点。
2.if后面误加分号
错误写法：
if (board[i][j] == w[0]); dfs(i, j, 0, board, w, flag);这个分号会让if变成空语句，导致dfs不受条件控制，每个格子都会执行。
正确写法：
if (board[i][j] == w[0]) { dfs(i, j, 0, board, w, flag); }3. 没有处理重复使用格子
题目要求同一个单元格不能重复使用。
所以需要flag或visited来记录当前路径中已经访问过的格子。
如果true表示已经访问，那么递归到下一个格子前应该判断：
!flag[x][y]4. 检查错了访问位置
准备从(i,j)走到(x,y)时，要检查的是下一个格子(x,y)是否已经访问：
!flag[x][y]不是检查当前格子：
flag[i][j]因为真正决定下一步能不能走的是目标位置。
5. 终止条件写成k == word.length
如果已经进入 DFS 后还要访问：
word[k]那么k == word.length时就会越界。
更自然的写法是：当前字符匹配成功后，判断它是不是最后一个字符：
if (k == word.length - 1) { ans = true; return; }复杂度分析
设网格大小为m x n，单词长度为L。
- 时间复杂度：
O(m * n * 4 * 3^(L - 1))。每个格子都可能作为起点；第一步最多有 4 个方向，之后因为不能走回已访问格子，每一步最多大约有 3 个方向。 - 空间复杂度：
O(m * n + L)。flag数组需要O(m * n)，递归栈深度最多为L。
复盘
这题的核心不是 DFS 框架本身，而是把 DFS 的状态定义清楚。
dfs(i, j, k)的含义是：
当前格子 board[i][j] 要匹配 word[k]有了这个定义，代码顺序就比较清楚：
1. 判断当前字符是否匹配 2. 判断是否已经匹配到最后一个字符 3. 标记当前格子已访问 4. 枚举四个方向继续搜索 5. 恢复当前格子的访问状态本次主要问题有两个：
1. 一开始只从 (0,0) 搜索，漏掉其他起点 2. 一开始没有正确维护 flag，导致格子可能被重复使用后面修正时，最关键的是统一flag的语义：
false = 没访问过 true = 当前路径已经访问过只要这个语义稳定，递归前判断!flag[x][y]，进入后标记，退出前恢复，回溯逻辑就不会乱。
Tips
矩阵回溯题可以先问自己三个问题：
1. 起点是不是固定的？如果不是，就要枚举所有起点。 2. 当前递归参数分别表示什么？ 3. 当前路径里哪些状态需要回溯恢复？对于这题，可以记住一句话：
每个格子负责匹配一个字符，当前路径用过的格子不能再走，退出当前路径时恢复现场。