力扣第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

分析

根据题意并没有好的简单的办法只能使用深度优先搜索一个一个匹配，以示例1为例，先是字母A发现匹配，然后分别向上下左右去找下一个匹配的，加入向下搜索发现不匹配那么就回溯到A继续搜索其它方向，直到搜索出单词返回true。

代码如下：

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        // 获取棋盘的行数和列数
        int rows = board.size();
        int cols = board[0].size();
        // 创建一个二维布尔数组用于标记每个位置是否被访问过
        vector<vector<bool>> visit(rows, vector<bool>(cols, false));

        // 遍历棋盘的每一个位置作为搜索的起点
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                // 从当前起点位置开始进行深度优先搜索（DFS）
                if (dfs(board, word, row, col, 0, visit)) {
                    // 如果找到了目标单词，则返回 true
                    return true;
                }
            }
        }
        // 如果遍历完所有起点位置都没有找到目标单词，则返回 false
        return false;
    }

    bool dfs(vector<vector<char>>& board, string word, int row, int col, int index, vector<vector<bool>>& visit) {
        // 如果当前索引等于目标单词的长度，说明找到了完整的单词
        if (index == word.length()) {
            return true;
        }

        // 如果当前坐标超出棋盘边界，或者当前字符不匹配，或者当前坐标已经被访问过，则返回 false
        int rows = board.size();
        int cols = board[0].size();
        if (row >= rows || row < 0 || col >= cols || col < 0 || board[row][col] != word[index] || visit[row][col]) {
            return false;
        }

        // 标记当前位置已被访问
        visit[row][col] = true;

        // 递归地探索四个方向（上下左右），查找是否可以继续匹配目标单词
        bool res = dfs(board, word, row + 1, col, index + 1, visit) || // 向下
                   dfs(board, word, row - 1, col, index + 1, visit) || // 向上
                   dfs(board, word, row, col + 1, index + 1, visit) || // 向右
                   dfs(board, word, row, col - 1, index + 1, visit);   // 向左

        // 回溯时，取消当前位置的访问标记
        visit[row][col] = false;

        // 返回是否找到了目标单词
        return res;
    }
};

解释注释

1.exist 方法：该方法负责在棋盘上查找是否存在目标单词。

首先获取棋盘的行数和列数，并创建一个二维布尔数组 visit 用于记录每个位置是否已经被访问过。
遍历棋盘上的每一个位置，将其作为 DFS 搜索的起点。
对每个起点调用 dfs 方法进行深度优先搜索，如果找到了目标单词，则返回 true。
如果遍历完所有位置后都没有找到目标单词，则返回 false。

2.dfs 方法：这是一个递归函数，用于从当前坐标进行深度优先搜索。

当 index 等于目标单词的长度时，说明找到了完整的单词，返回 true。
如果当前位置超出边界、字符不匹配或已经被访问过，则返回 false。
标记当前位置已被访问，然后递归探索上下左右四个方向。
递归完成后，取消当前位置的访问标记（回溯），以便其他路径可以访问到该位置。
返回是否找到目标单词。