每日OJ题_DFS爆搜深搜回溯剪枝⑥_力扣79. 单词搜索

目录

力扣79. 单词搜索

解析代码

力扣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 更大的情况下可以更快解决问题？

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {

    }
};

解析代码

        思路：需要假设每个位置的元素作为第一个字母，然后向相邻的四个方向进行递归，并且不能出现重复用同一个位置的元素。通过深度优先搜索的方式，不断地枚举相邻元素作为下一个字母出现的可能性，并在递归结束时回溯，直到枚举完所有可能性，得到正确的结果。

递归函数流程：

1. 遍历每个位置，标记当前位置并将当前位置的字母作为首字母进行递归，并且在回溯时撤回标记。
2. 在每个递归的状态中，我们维护一个步数 step，表示当前已经处理了几个字母。若当前位置的字母与字符串中的第 step 个字母不相等，则返回 false。若当前 step 的值与字符串长度相等，表示存在一种路径使得 word 成立，返回 true。
3. 对当前位置的上下左右四个相邻位置进行递归，若递归结果为 true，则返回 true。
4. 若相邻的四个位置的递归结果都为 false，则返回 false。

        特别地，如果使用将当前遍历到的字符赋值为空格，并在回溯时恢复为原来的字母的方法，则在递归时不会重复遍历当前元素，可达到不使用标记数组的目的。

class Solution {
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    bool vis[7][7];
    int m, n;

public:
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size(), n = board[0].size();
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(board[i][j] == word[0])
                {
                    vis[i][j] = true;
                    if(dfs(board, i, j, word, 1) == true)
                        return true;
                    vis[i][j] = false;
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board, int i, int j, string& word, int pos)
    {   // pos是遍历到了word的第几个字符
        if(pos == word.size())
            return true;
        for(int k = 0; k < 4; ++k)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == word[pos] && !vis[x][y])
            {
                vis[x][y] = true;
                if(dfs(board, x, y, word, pos + 1) == true)
                    return true;
                vis[x][y] = false;
            }
        }
        return false;
    }
};