79. 单词搜索
一句话套路网格 DFS + 占位符标记,回溯时还原
题目描述
给定一个 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 = "SEE" 输出:true
示例 3:
输入:board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB" 输出:false
提示:
m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board和word仅由大小写英文字母组成
进阶:你可以使用搜索剪枝的技术来优化解决方案,使其在 board 更大的情况下可以更快解决问题?
思路
时间
O(mn·3^L)(每步最多 3 个新方向)空间
O(L)思路
网格 DFS + 回溯。用「临时把格子改成一个非字母占位符」代替 visited 数组,省空间;
但必须还原,否则会破坏入参(多次调用/多次分支都会踩这个坑)。
剪枝
先统计词频,若某个字符在 board 里不够多,直接返回 false(高频加分项,见下方代码)。
图解
矩阵(来自本仓库测试数据,红色格子 = 0)
逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0079 {
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
if (board.empty() || board[0].empty()) return false; // 空盘搜不出任何东西(题面保证 m,n ≥ 1)
// 剪枝:词频不够就根本不用搜(面试里这一句常常是真正的加分点)
int need[26] = {};
for (char c : word) ++need[(unsigned char)c - 'A'];
for (const auto& row : board)
for (char c : row)
if (c >= 'A' && c <= 'Z') --need[(unsigned char)c - 'A'];
for (int i = 0; i < 26; ++i)
if (need[i] > 0) return false;
const int R = (int)board.size(), C = (int)board[0].size();
for (int i = 0; i < R; ++i)
for (int j = 0; j < C; ++j)
if (dfs(board, word, i, j, 0, R, C)) return true;
return false;
}
private:
static bool dfs(vector<vector<char>>& b, const string& w, int i, int j, int k, int R, int C) {
if (k == (int)w.size()) return true; // 整个词都匹配上了
if (i < 0 || j < 0 || i >= R || j >= C) return false;
if (b[i][j] != w[k]) return false;
char saved = b[i][j];
b[i][j] = '#'; // 占位:同一格不能在一条路径里用两次
bool found = dfs(b, w, i + 1, j, k + 1, R, C) || dfs(b, w, i - 1, j, k + 1, R, C) ||
dfs(b, w, i, j + 1, k + 1, R, C) || dfs(b, w, i, j - 1, k + 1, R, C);
b[i][j] = saved; // 回溯还原 —— 漏了这行,本格被永久标成 '#',其他分支再用它就得到假阴性
return found;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0079::Solution s;
vector<vector<char>> b{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
CHECK_TRUE(s.exist(b, "ABCCED"));
CHECK_TRUE(s.exist(b, "SEE"));
CHECK_FALSE(s.exist(b, "ABCB")); // 盘上只有一个 B,而且已经被走过 —— 同一格不能在一条路径里用两次
CHECK_FALSE(s.exist(b, "ABCEZ")); // 词里有 board 上不存在字符
CHECK_TRUE(s.exist(b, "A"));
CHECK_FALSE(s.exist(b, "AAAA")); // 盘上只有 2 个 A,词频剪枝直接拒掉
vector<vector<char>> emptyBoard;
CHECK_FALSE(s.exist(emptyBoard, "A")); // 空盘:不守卫就是 board[0] 越界