79. 单词搜索
4 min
题目
解法：DFS回溯
思路
深度优先搜索（DFS）结合回溯法，通过原地修改网格标记访问状态来避免重复使用单元格。
该方法正确性基于穷举所有可能路径：从每个单元格出发，递归探索四个方向的所有可能路径。当路径上的字符与单词完全匹配且长度一致时即找到解。标记已访问单元格确保不重复使用，回溯时恢复状态保证不同搜索路径互不干扰，从而不会遗漏任何潜在解。
- Step 1: 遍历网格中每个单元格作为搜索起点
- Step 2: 在DFS中检查边界和字符匹配，若匹配则继续递归
- Step 3: 临时修改当前单元格字符为特殊标记’#‘防止重复访问
- Step 4: 向上下左右四个方向递归搜索下一个字符
- Step 5: 回溯时恢复单元格原始字符，尝试其他路径
复杂度
- 时间复杂度: ，其中m、n为网格维度，k为单词长度。最坏情况下需遍历所有起点并探索四个方向的所有可能路径。
- 空间复杂度: ，递归调用栈的最大深度为单词长度，用于保存搜索路径状态。
代码
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int m = board.size();
int n = board[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs(board, i, j, word, 0)) {
return true;
}
}
}
return false;
}
bool dfs(vector<vector<char>>& board, int i, int j, const string& word, int k) {
int m = board.size();
int n = board[0].size();
// 越界或字母不匹配
if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[k]) {
return false;
}
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int m = board.size();
int n = board[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs(board, i, j, word, 0)) {
return true;
}
}
}
return false;
}
bool dfs(vector<vector<char>>& board, int i, int j, const string& word, int k) {
int m = board.size();
int n = board[0].size();
// 越界或字母不匹配
if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[k]) {
return false;
}
// 找到最后一个字符
if (k == word.size() - 1) {
return true;
}
// 标记已访问（防止走回头路）
char temp = board[i][j];
board[i][j] = '#';
// 尝试四个方向
bool found = dfs(board, i + 1, j, word, k + 1) ||
dfs(board, i - 1, j, word, k + 1) ||
dfs(board, i, j + 1, word, k + 1) ||
dfs(board, i, j - 1, word, k + 1);
// 回溯
board[i][j] = temp;
return found;
}
};