专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
以前我面试的时候无论结果如何都不会自动和hr联系，因为我觉得如果过了hr肯定会联系我，如果没过，就算我主动联系也没用。今天看到一个00后的学生和hr的对话让我感觉到啥叫高情商，看似啥都没问，实则啥都问了。
在网上也经常看到不少面试后主动联系HR而争取到offer的，这种情况下一般是候选人都比较优秀，hr还在犹豫该选谁，这个时候主动问候还是有机会的。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第79题：单词搜索。
问题描述
来源：LeetCode第79题
难度：中等
给定一个 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 = "ABCB" 输出：false
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成
问题分析
这题是让判断给定的单词是否在二维网格中，这是一道搜索问题，前面我们也讲过各种搜索算法：
(BFS)
这题我们可以使用回溯算法，对于当前点沿着他的上下左右 4 个方向查找，如果最后能找到给定的单词就返回true，否则就返回false，如下图所示。
这里要注意同一单元格类的字母不能被重复使用，所以我们查找之后还需要标记一下。由于单词的起始字母在网格中的哪个位置我们并不知道，所以需要以网格中的每一个位置为起始点进行查找。
JAVA：
public boolean exist(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++) { // 从(i,j)这个坐标开始查找，如果找到直接返回true。 if (dfs(board, words, i, j, 0)) return true; } } return false; } // (i,j)表示当前查找的坐标，index表示查找单词的第几个字母。 boolean dfs(char[][] board, char[] words, int i, int j, int index) { // 边界的判断，如果越界直接返回false。index表示的是查找到字符串words的第几个字符， // 如果这个字符不等于board[i][j]，说明验证这个坐标路径是走不通的，直接返回false。 if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != words[index]) return false; // 如果words的每个字符都查找完了，直接返回true if (index == words.length - 1) return true; // 把当前坐标的值保存下来，为了在最后复原。 char tmp = board[i][j]; // 修改当前坐标的值，主要为了防止当前网格被重复查找。 board[i][j] = '.'; // 走递归，沿着当前坐标的上下左右4个方向查找 boolean res = dfs(board, words, i - 1, j, index + 1)// 上 || dfs(board, words, i + 1, j, index + 1)// 下 || dfs(board, words, i, j - 1, index + 1)// 左 || dfs(board, words, i, j + 1, index + 1);// 右 // 递归之后再把当前的坐标复原。 board[i][j] = tmp; return res;// 返回查找的结果。 }C++：
public: bool exist(vector char >>& board, string word) { // 遍历网格的所有位置，以每一个位置为起始点进行查找。 for (int i = 0; i < board.size(); i++) { for (int j = 0; j < board[0].size(); j++) { // 从(i,j)这个坐标开始查找，如果找到直接返回true。 if (dfs(board, word, i, j, 0)) return true; } } return false; } // (i,j)表示当前查找的坐标，index表示查找单词的第几个字母。 bool dfs(vector char >>& board, string word, int i, int j, int index) { // 边界的判断，如果越界直接返回false。index表示的是查找到字符串word的第几个字符， // 如果这个字符不等于board[i][j]，说明验证这个坐标路径是走不通的，直接返回false。 if (i >= board.size() || i < 0 || j >= board[0].size() || j < 0 || board[i][j] != word[index]) return false; // 如果words的每个字符都查找完了，直接返回true if (index == word.size() - 1) return true; // 把当前坐标的值保存下来，为了在最后复原。 char tmp = board[i][j]; // 修改当前坐标的值，主要为了防止当前网格被重复查找。 board[i][j] = '.'; // 走递归，沿着当前坐标的上下左右4个方向查找 bool res = dfs(board, word, i - 1, j, index + 1)// 上 || dfs(board, word, i + 1, j, index + 1)// 下 || dfs(board, word, i, j - 1, index + 1)// 左 || dfs(board, word, i, j + 1, index + 1);// 右 // 递归之后再把当前的坐标复原。 board[i][j] = tmp; return res;// 返回查找的结果。 }Python：
# 79. 单词搜索 def exist(self, board: List[List[str]], word: str) -> bool: def dfs(i: int, j: int, index: int): if index == len(word): return True # 单词的所有字符全部查找完了。 # 不能越界，不能访问到矩阵的外面 if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]): return False # 如果查找字符不一样，返回false。 if board[i][j] != word[index]: return False tmp = board[i][j] # 把原来字符记录下来 board[i][j] = '#' # 表示已经被访问过了，防止重复访问。 exist = (dfs(i - 1, j, index + 1) # 上 or dfs(i + 1, j, index + 1) # 下 or dfs(i, j - 1, index + 1) # 左 or dfs(i, j + 1, index + 1)) # 右 board[i][j] = tmp # 回溯算法，还原，撤销选择 return exist # 以网格的任何一个位置为起始点进行查找。 for i in range(0, len(board)): for j in range(0, len(board[i])): if dfs(i, j, 0): return True return False # 如果都查找不到，返回false。笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。