0079. Word Search
=================
题目信息
--------
:题号: 0079. 单词搜索
:难度: Medium
:主题: 矩阵、深度优先搜索、回溯
:原题: `LeetCode 0079 `_
:重点: 从枚举起点,推导到路径占用回溯,再加入频次与搜索方向剪枝
题目重述
--------
给定一个 ``m × n`` 的字符矩阵 ``board`` 和字符串 ``word``,判断矩阵中是否存在一条路径,
使路径上的字符按顺序组成 ``word``。
路径可以从任意格子开始。每一步只能移动到当前格子的上、下、左、右相邻格子;
同一个格子在同一条路径中最多使用一次。
约束如下:
* ``1 <= m, n <= 6``;
* ``1 <= word.length <= 15``;
* ``board`` 和 ``word`` 只包含英文字母。
自建示例
--------
.. code-block:: text
输入:
board = [["A","X","C"],
["D","E","F"],
["G","H","I"]]
word = "AXCFI"
输出:true
可以沿 ``A -> X -> C -> F -> I`` 移动,每一步都进入上下左右相邻格子。
.. code-block:: text
输入:
board = [["A","B"],
["C","D"]]
word = "ABA"
输出:false
最后一个 ``A`` 只能复用起点,但同一条路径中不能重复使用格子。
.. code-block:: text
输入:
board = [["A","A"],
["B","C"]]
word = "AAA"
输出:false
矩阵中只有两个 ``A``,字符频次预检即可判定无解。
C++ 实现
--------
.. code-block:: cpp
#include
#include
#include
#include
class Solution {
private:
bool visitedDfs(
const std::vector>& board,
const std::string& word,
int row,
int col,
int index,
std::vector>& visited
) {
int rows = static_cast(board.size());
int cols = static_cast(board[0].size());
if (row < 0 || row >= rows || col < 0 || col >= cols) {
return false;
}
if (visited[row][col] || board[row][col] != word[index]) {
return false;
}
if (index + 1 == static_cast(word.size())) {
return true;
}
visited[row][col] = true;
bool found =
visitedDfs(board, word, row + 1, col, index + 1, visited) ||
visitedDfs(board, word, row - 1, col, index + 1, visited) ||
visitedDfs(board, word, row, col + 1, index + 1, visited) ||
visitedDfs(board, word, row, col - 1, index + 1, visited);
visited[row][col] = false;
return found;
}
bool searchWithVisited(
const std::vector>& board,
const std::string& word
) {
int rows = static_cast(board.size());
int cols = static_cast(board[0].size());
std::vector> visited(
rows,
std::vector(cols, false)
);
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
if (visitedDfs(board, word, row, col, 0, visited)) {
return true;
}
}
}
return false;
}
bool inPlaceDfs(
std::vector>& board,
const std::string& word,
int row,
int col,
int index
) {
int rows = static_cast(board.size());
int cols = static_cast(board[0].size());
if (row < 0 || row >= rows || col < 0 || col >= cols) {
return false;
}
if (board[row][col] != word[index]) {
return false;
}
if (index + 1 == static_cast(word.size())) {
return true;
}
char saved = board[row][col];
board[row][col] = '\0';
bool found =
inPlaceDfs(board, word, row + 1, col, index + 1) ||
inPlaceDfs(board, word, row - 1, col, index + 1) ||
inPlaceDfs(board, word, row, col + 1, index + 1) ||
inPlaceDfs(board, word, row, col - 1, index + 1);
board[row][col] = saved;
return found;
}
bool searchInPlace(
std::vector>& board,
const std::string& word
) {
int rows = static_cast(board.size());
int cols = static_cast(board[0].size());
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
if (inPlaceDfs(board, word, row, col, 0)) {
return true;
}
}
}
return false;
}
bool frequencyPrunedSearch(
std::vector>& board,
std::string word
) {
int rows = static_cast(board.size());
int cols = static_cast(board[0].size());
if (static_cast(word.size()) > rows * cols) {
return false;
}
std::array available{};
for (const auto& row : board) {
for (char ch : row) {
++available[static_cast(ch)];
}
}
std::array remaining = available;
for (char ch : word) {
int code = static_cast(ch);
if (--remaining[code] < 0) {
return false;
}
}
int first = static_cast(word.front());
int last = static_cast(word.back());
if (available[first] > available[last]) {
std::reverse(word.begin(), word.end());
}
return searchInPlace(board, word);
}
public:
bool exist(
std::vector>& board,
std::string word
) {
return frequencyPrunedSearch(board, word);
}
};
题解
----
路径状态
~~~~~~~~
枚举每个格子作为起点。递归状态 ``dfs(row, col, index)`` 表示:
* ``word[0:index)`` 已由当前路径匹配;
* 现在尝试用 ``board[row][col]`` 匹配 ``word[index]``;
* 当前路径已经使用过的格子不能再次进入。
越界、字符不匹配或格子已被当前路径占用时,该分支立即失败。
当前位置匹配最后一个字符时,完整单词已经形成,可以返回成功。
选择与恢复
~~~~~~~~~~
字符匹配后,需要暂时占用当前格子,再尝试四个方向。独立访问矩阵直接记录占用状态;
原地方案把当前字符暂时改成字符域外的 ``'\0'``,从而复用矩阵本身保存状态。
四个方向搜索结束后,必须恢复原字符。成功分支也先写入 ``found``,恢复后再返回,
因此公开方法结束时矩阵内容与输入一致。
.. list-table::
:header-rows: 1
* - 阶段
- 当前状态
- 动作
* - 匹配
- 当前字符等于 ``word[index]``
- 暂时占用当前格
* - 扩展
- 还未匹配完整单词
- 尝试四个相邻格
* - 回退
- 当前分支成功或失败
- 恢复当前格
* - 继续
- 回到上一层
- 尝试下一方向或起点
格子不可复用
~~~~~~~~~~~~
只禁止立即返回上一格并不充分,因为路径可能绕一圈后再次进入更早的格子。
访问标记覆盖整条当前路径,任何已占用坐标都会被后续递归拒绝。
回溯离开一层时恢复标记,使同一格子仍可被其他起点或其他分支使用。
限制只作用于单条搜索路径,不会永久删除矩阵位置。
起点与方向剪枝
~~~~~~~~~~~~~~
单词首字符可能位于任意格子,因此所有起点都要被考虑;不匹配首字符的起点会在递归入口立即失败。
搜索前先比较字符总量。若单词长度超过格子数,或某字符需求超过矩阵中的可用数量,
路径一定不存在,可以直接返回 ``false``。
一条路径正向拼出 ``word``,反向沿同一路径就会拼出逆序单词。
因此可以从首尾字符中出现次数更少的一端开始搜索,减少候选起点和早期分支,
同时不改变答案真假。
搜索完整性
~~~~~~~~~~
对任意可行路径,外层循环会枚举到它的起点。递归在每一步完整尝试四个相邻格,
其中必然包含目标路径的下一格;访问标记只排除路径中已经使用的坐标,
所以合法路径不会被剪掉。
同一条坐标路径只按确定的起点和移动序列被访问。题目只要求判断是否存在,
找到任意完整路径后即可停止。
复杂度
~~~~~~
设矩阵有 ``m * n`` 个格子,单词长度为 ``L``。每个格子都可能作为起点;
首步之后通常最多继续到三个未占用方向,最坏时间可写为 ``O(mn * 3^L)``。
频次预检需要 ``O(mn + L)`` 时间。递归栈深度最多为 ``L``,原地标记除递归栈外
只使用固定大小的频次数组,因此额外空间为 ``O(L)``。