【回溯+剪枝】单词搜索，你能用递归解决吗？
【回溯+剪枝】单词搜索，你能用递归解决吗？
79. 单词搜索
给定一个 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 更大的情况下可以更快解决问题？
解题思路：回溯（深搜） + 剪枝
毫无疑问这道题就是要使用深搜，或者说是回溯，它们两个的思想都是一样的，从同一个起点出发，然后一直往更深层次去遍历！但是因为这道题和那种迷宫问题不太一样，迷宫问题是只有一个入口，但是这道题入口可能不是第一个元素，可能是其它的元素开头，所以我们必须 在主调用函数中进行一个 for 循环遍历每个元素为入口的路径，如果出现了成功的情况，则直接返回即可，反之说明每个入口都是不成功匹配的，则直接返回一个 false 即可，如下所示：
bool exist(vector<vector<char>>& board, string word)
{
for(int i = 0; i < board.size(); ++i)
{
for(int j = 0; j < board[i].size(); ++j)
{
if(递归函数的返回值 == true)
return true;
}
}
return false;
} 也就是说此时需要设计一个 dfs() 函数，帮助我们返回以某个元素为入口的路径中是否存在匹配的字符串！这个通过前面的刷题量，其实并不难解决，我们可以分下面三步走：
函数头的设计：
因为我们需要递归函数返回一个布尔值，所以返回值就是 bool 类型的！
其次少不了的就是题目给的网格 board 以及要查找的字符串 word。
然后因为我们需要知道当前递归函数走到了目标字符串的哪个位置，所以需要一个 index 变量来标记！
此外因为我们需要判断当前位置是否越界，所以需要有当前位置在网格中的坐标，所以需要 x 和 y 来表示！
bool dfs(vector<vector<char>>& board, string& word, int index, int x, int y);递归函数出口：
因为这道题要求说同一个单元格内的字母不允许被重复使用，所以我们需要一个 全局的布尔类型二维数组 used 来标记当前位置是否已经走过，这样子往下的路径就能知道哪些该走哪些不该走！
然后主要就是判断以下内容：
- 当前在网格中的坐标是不是越界了
- 当前元素是否已经走过了
- 当前元素是否为目标字符串中对应的字符
如果出现其中一个不符合的话，则直接 return false 即可！
// 递归函数出口
if(x < 0 || x == board.size() || y < 0 || y == board[x].size() || used[x][y] == true || board[x][y] != word[index])
return false;函数体的内容：
- 函数体要做的事情无非就是进行处理当前元素、递归、回溯操作。
- 其中处理当前元素对于这道题来说就是标记进行当前元素已经走过，也就是将
used[x][y] = true即可！ - 递归操作的话，这里我们先判断一下是否
index已经走完字符串，是的话说明找到了符合要求的（因为不符合的在函数出口已经被筛掉了，能到这里就是符合的），则直接返回正确即可；或者递归的子函数中也找到了字符串，那么也直接返回正确！ - 对于回溯操作的话，只有当上面没找到字符串，才对当前元素进行恢复现场，然后返回失败给上一层，表示当前的路走不通，所以设置完
used[x][y] = false之后，就直接返回错误即可。
- 其中处理当前元素对于这道题来说就是标记进行当前元素已经走过，也就是将
完整代码如下所示：
class Solution {
private:
bool used[6][6]; // 标记当前位置是否已经走过
public:
bool exist(vector<vector<char>>& board, string word) {
for(int i = 0; i < board.size(); ++i)
{
for(int j = 0; j < board[i].size(); ++j)
{
if(dfs(board, word, 0, i, j))
return true;
}
}
return false;
}
bool dfs(vector<vector<char>>& board, string& word, int index, int x, int y)
{
// 递归函数出口
if(x < 0 || x == board.size() || y < 0 || y == board[x].size() || used[x][y] == true || board[x][y] != word[index])
return false;
used[x][y] = true; // 标记进行当前元素已经走过
// 如果走完字符串，说明找到了；或者递归的子函数中找到了字符串，则直接返回true
if(index == word.size() - 1 ||
dfs(board, word, index + 1, x + 1, y) ||
dfs(board, word, index + 1, x, y + 1) ||
dfs(board, word, index + 1, x - 1, y) ||
dfs(board, word, index + 1, x, y - 1))
return true;
// 只有当上面没找到字符串，才对当前元素进行恢复现场，然后返回失败给上一层，表示当前的路走不通
used[x][y] = false;
return false;
}
};腾讯云开发者
