难度中等656
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true示例 2：
输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false提示：
m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board和word仅由大小写英文字母组成
注意：本题与主站 79 题相同：https://leetcode-cn.com/problems/word-search/
思路：
本问题是典型的矩阵搜索问题，可使用 深度优先搜索（DFS）+ 剪枝 解决。
深度优先搜索： 可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。 剪枝： 在搜索中，遇到 这条路不可能和目标字符串匹配成功 的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为 可行性剪枝 。
步骤：
- 递归参数： 当前元素在矩阵
board中的行列索引i和j，当前目标字符在word中的索引k。 - 终止条件：
- 返回 false ： (1) 行或列索引越界 (2) 当前矩阵元素与目标字符不同 (3) 当前矩阵元素已访问过 （ 3 可合并至 2 ） 。
- 返回 true ：
k = len(word) - 1，即字符串word已全部匹配。
- 递推工作：
- 标记当前矩阵元素： 将
board[i][j]修改为 空字符''，代表此元素已访问过，防止之后搜索时重复访问。 - 搜索下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，使用 或 连接 （代表只需找到一条可行路径就直接返回，不再做后续 DFS ），并记录结果至 res 。
- 还原当前矩阵元素： 将
board[i][j]元素还原至初始值，即word[k]。
- 标记当前矩阵元素： 将
- 返回值： 返回布尔量
res，代表是否搜索到目标字符串。
使用空字符（Python: '' , Java/C++: '\0' ）做标记是为了防止标记字符与矩阵原有字符重复。当存在重复时，此算法会将矩阵原有字符认作标记字符，从而出现错误。
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
for(int row = 0; row < board.size(); ++row)
{
for(int col = 0; col < board[0].size(); ++col)
{
if(recursion(board, word, 0, row, col)) //用子函数去递归解决
return true;
}
}
return false;
}
bool recursion(vector<vector<char>>& b, string w, int i, int row, int col)
{
if(row < 0 || row >= b.size() || col < 0 || col >= b[0].size())
return false;
//这个判断必须放在判断越界的后面，否则会造成越界访问。。。
if(b[row][col] != w[i])
return false;
//如果字符串遍历完了则返回true
if(i == w.size() - 1)
return true;
b[row][col] = '\0';
bool tmp = recursion(b, w, i+1, row+1, col) ||
recursion(b, w, i+1, row-1, col) ||
recursion(b, w, i+1, row, col+1) ||
recursion(b, w, i+1, row, col-1);
b[row][col] = w[i];
return tmp;
}
};-
M,N 分别为矩阵行列大小， KK 为字符串
word长度。 -
时间复杂度 O(MN * 3^K) ： 最差情况下，需要遍历矩阵中长度为 KK 字符串的所有方案，时间复杂度为 O(3^K)；矩阵中共有 MN 个起点，时间复杂度为 O(MN) 。
-
空间复杂度 O(K) ： 搜索过程中的递归深度不超过 K ，因此系统因函数调用累计使用的栈空间占用O(K) （因为函数返回后，系统调用的栈空间会释放）。最坏情况下 K = MN ，递归深度为 MN ，此时系统栈使用 O(MN) 的额外空间。
