大家好，我是吴师兄。
今天看到一个小伙伴去蔚来面试的经历，虽然跪了，但经验还是值得参考的，一方面八股文考察的内容属于大众熟悉的高频知识点，另外一方面算法题还挺难的，今天来练习一下。
来看二面的算法题，题目描述是这样的。
字母迷宫游戏初始界面记作
m x n
二维字符串数组
grid
，请判断玩家是否能在
grid
中找到目标单词
target
。注意：寻找单词时
必须
按照字母顺序，通过水平或垂直方向相邻的单元格内的字母构成，同时，同一个单元格内的字母
不允许被重复使用
。
示例 1：
输入：grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], target = "ABCCED"
输出：true
示例 2：
输入：grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], target = "SEE"
输出：true
示例 3：
输入：grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], target = "ABCB"
输出：false
提示：
-
-
-
-
-
grid
和
target
仅由大小写英文字母组成
本题的主要策略是使用深度优先搜索（DFS）。来，我们逐步拆解：
首先是主函数 wordPuzzle：
-
wordPuzzle
函数接收一个字符矩阵
board
和一个目标单词
word
。
-
将目标单词转换为字符数组
words
，方便逐个字符比对。
-
使用双层循环遍历矩阵的每一个元素，以每个元素为起点，调用
dfs
函数进行深度优先搜索。
-
如果在某个起点开始的搜索成功找到了目标单词，则函数返回
true
；如果所有起点都搜索失败，则返回
false
。
接下来是 DFS 函数：
-
dfs
函数是实现深度优先搜索的核心，参数包括矩阵
board
、目标单词的字符数组
word
、当前位置
(i, j)
和当前目标字符的索引
k
。
-
首先检查边界条件，包括位置
(i, j)
是否越界以及当前位置的字符是否与目标字符匹配。如果不满足条件，返回
false
。
-
如果当前字符是目标单词的最后一个字符并且匹配成功，则整个搜索过程成功，返回
true
。
-
在当前位置上标记已访问（例如，将字符改为
#
），然后递归地在四个方向上搜索下一个目标字符。
-
在返回之前，将当前位置的字符还原，以免影响其他路径的搜索。
-
返回四个方向搜索的结果的逻辑或（
||
），即如果任一方向搜索成功，则整体搜索成功。
简而言之，这段代码通过从矩阵的每个点出发，尝试所有可能的路径来查找目标单词。它巧妙地利用了递归和回溯，逐步深入，一旦发现当前路径不可行，就回退，尝试其他可能，直到找到一条正确的路径或确定无解。
关于 DFS ，我都会给算法训练营的同学举一个例子：
想象一下，你在一个迷宫里寻找一条路，这条路上的指示牌顺序排列能告诉你如何从起点到达终点。你需要走遍每一个岔口，尝试每条路，直到找到正确的路径。如果某条路走不通，你就返回上一个岔口，尝试其他方向。这段代码，就是在用程序的方式，帮你在字符组成的迷宫中，找到拼出目标单词的那条路。
具体代码如下：
class Solution {
public boolean wordPuzzle(char[][] board, String word) {
// 先将字符串进行拆分，一个一个元素进行匹配
char[] words = word.toCharArray();
// 通过两层嵌套，覆盖所有的情况
for(int i = 0 ; i < board.length; i++) {
for(int j = 0 ; j < board[0].length ; j++) {
// 以该元素为起始点，递归检查是否符合要求
if(dfs(board,words,i,j,0)) return true;
}
}
return false;
}
boolean dfs(char[][] board, char[] word, int i, int j, int k) {
// 边界情况判断
// 行越界
// 列越界
// 矩阵元素已访问过
if( i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
// 之前已经和目标字符串匹配成功了 length - 1 个字符，此时又匹配成功了最后一个元素，直接返回结果
if( k == word.length - 1) return true;
// 标记当前矩阵元素，将其修改为特殊字符 # ，代表此元素已访问过，防止之后搜索时重复访问。
board[i][j] = '#';
// 搜索元素的四个方向 上 左 下 右，匹配下一个目标元素
boolean res = dfs(board,word,i,j-1,k+1)
|| dfs(board,word,i - 1 ,j ,k + 1)
|| dfs(board,word,i , j + 1 ,k + 1)
|| dfs(board,word, i + 1 ,j , k + 1);
// 回退时还原当前矩阵元素
board[i][j] = word[k];
// 返回结果
return res;
}
}
