大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位脉友吐槽被公司告知在裁员名单里，后面又说项目太复杂暂时不裁了，把楼主搞的一脸懵，第一次遇到这种骚操作，不知道后面还会不会被裁。
评论区的脉友纷纷出谋划策，建议楼主要一直让项目复杂下去，防御性代码要写起来。大部分脉友还是很清醒，认为楼主要抓紧看机会了，项目结束肯定会被裁。好巧不巧，我也见过类似情况，一位同事被沟通完大礼包的第二天又被撤回了，就是因为那段时间项目缺少一个打杂的，项目结束以后那位同事如愿拿到了大礼包。
25届秋招已经开始了，我组织了一个秋招群，大家可以交流学习心得、面试经验，分享工作机会，有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档，以及投递入口，每天都会更新，大家只要按照这个文档海投就可以了。
大家互帮互助相信一定可以拿下秋招！计算机相关专业的同学可以 点击底部的「阅读原文」 加群。
言归正传，今天我们来分享一道高频面试题「单词搜索」。
题目描述
给定一个 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搜索，搜索到目标单词就返回true，否则，所有的路径都搜索完也没搜到目标单词就返回false。
假设二维数组board = [['F', 'C', 'S'], ['F', 'E', 'D'], ['A', 'B', 'C']]。
要搜索的字符串word = "BEF"，那么从board边界坐标(2, 1)即字符B开始，按照下右上左的顺序进行dfs的过程如下图，因为每个字符最多有四个相邻字符，所以搜索树是一个四叉树。
从字符B搜索到字符C发现不匹配，把字符C置为未被访问的状态，回溯到字符B，接着对字符E进行搜索，直到搜索到字符F，整个word被搜索到，返回true。
定义变量i为递归的深度，也表示word的第i个字符，row为二维数组board的行，col为二维数组board的列。
递归结束的条件如下：
递归深度 i == word.length()，说明在board中搜索到了word，结束搜索返回true。递归深度 i < word.length()，如果坐标(row, col)在board边界之外 或board[row][col] != word[i]或 坐标(row, col)已被访问过 就结束搜索返回false，否则继续向四周搜索。
下面我们给出c++和python的两种代码实现。
C++代码
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int rows = board.size();
int cols = board[0].size();
vector<vector<bool>> visit(rows, vector<bool>(cols, false));
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col ) {
if (dfs(row, col, 0, board, word, visit)) {
return true;
}
}
}
return false;
}
//row：board的行，col：board的列，i：递归的深度也是word的第i个字符，visit：保存board中元素是否访问过
bool dfs(int row, int col, int i, vector<vector<char>>& board, string& word, vector<vector<bool>>& visit) {
if (i == word.length()) {
return true;
}
int rows = board.size();
int cols = board[0].size();
if (row >= rows || row < 0 || col >= cols || col < 0 || board[row][col] != word[i] || visit[row][col]) {
return false;
}
visit[row][col] = true;
bool res = false;
//向下搜索
res |= dfs(row + 1, col, i + 1, board, word, visit);
//向右搜索
res |= dfs(row, col + 1, i + 1, board, word, visit);
//向上搜索
res |= dfs(row - 1, col, i + 1, board, word, visit);
//向左搜索
res |= dfs(row, col - 1, i + 1, board, word, visit);
visit[row][col] = false;
return res;
}
};
python代码
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
rows = len(board)
cols = len(board[0])
visit = [[False] * cols for _ in range(rows)] # 记录访问过的位置
for row in range(rows):
for col in range(cols):
if self.dfs(row, col, 0, board, word, visit):
return True
return False
def dfs(self, row, col, i, board, word, visit):
if i == len(word): # 如果已经匹配到了word的最后一个字符，说明匹配成功
return True
rows = len(board)
cols = len(board[0])
if (row < 0 or row >= rows or col < 0 or col >= cols or # 边界条件判断
board[row][col] != word[i] or visit[row][col]): # 当前字符不匹配或者已经访问过
return False
visit[row][col] = True # 标记当前位置为已访问
res = (self.dfs(row + 1, col, i + 1, board, word, visit) or # 向下搜索
self.dfs(row, col + 1, i + 1, board, word, visit) or # 向右搜索
self.dfs(row - 1, col, i + 1, board, word, visit) or # 向上搜索
self.dfs(row, col - 1, i + 1, board, word, visit)) # 向左搜索
visit[row][col] = False # 回溯，取消标记
return res
复杂度分析
时间复杂度： board中的每一个元素都要进行深度优先搜索，这里的深搜使用递归来实现的，这里的递归展开来是一个高度为k的四叉树，所以时间复杂度为O(mn4k)，其中m是board的行数，n是board的列数。
空间复杂度： 借用了一个visit数组和递归调用栈，所以空间复杂度为O(mn)，递归调用栈和word的长度有关，一般不会比mn长。其中m是visit的行数，n是visit的列数。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
