【回溯+剪枝】单词搜索，你能用递归解决吗？

79. 单词搜索

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.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 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() 函数，帮助我们返回以某个元素为入口的路径中是否存在匹配的字符串！这个通过前面的刷题量，其实并不难解决，我们可以分下面三步走：

1. 函数头的设计：

   • 因为我们需要递归函数返回一个布尔值，所以返回值就是 bool 类型的！

   • 其次少不了的就是题目给的网格 board 以及要查找的字符串 word。

   • 然后因为我们需要知道当前递归函数走到了目标字符串的哪个位置，所以需要一个 index 变量来标记！

   • 此外因为我们需要判断当前位置是否越界，所以需要有当前位置在网格中的坐标，所以需要 x 和 y 来表示！

     bool dfs(vector<vector<char>>& board, string& word, int index, int x, int y);
     

2. 递归函数出口：

   • 因为这道题要求说同一个单元格内的字母不允许被重复使用，所以我们需要一个 全局的布尔类型二维数组 used 来标记当前位置是否已经走过，这样子往下的路径就能知道哪些该走哪些不该走！

   • 然后主要就是判断以下内容：

     1. 当前在网格中的坐标是不是越界了
     2. 当前元素是否已经走过了
     3. 当前元素是否为目标字符串中对应的字符

   • 如果出现其中一个不符合的话，则直接 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;
     

3. 函数体的内容：

   • 函数体要做的事情无非就是进行处理当前元素、递归、回溯操作。
     • 其中处理当前元素对于这道题来说就是标记进行当前元素已经走过，也就是将 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; // 标记进行当前元素已经走过// 如果走完字符串，说明找到了；或者递归的子函数中找到了字符串，则直接返回trueif(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;}
};