题目描述给定一个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. 当前路径里哪些状态需要回溯恢复对于这题可以记住一句话每个格子负责匹配一个字符当前路径用过的格子不能再走退出当前路径时恢复现场。
)
