力扣79. 单词搜索-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣79. 单词搜索。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

回溯

思路：

定义函数 check(i,j,k) 为网格 (i,j) 位置出发能够搜索到单词 word(k)，如果搜索到返回 true，否则返回 false；
搜索规则：
- 【R1】如果 board[i][j] != word[k]，直接返回 false；
- 【R2】如果当前已经访问到字符串的末尾，且对应字符依然匹配，此时直接返回 true；
- 【R3】否则，遍历当前位置的所有相邻位置。如果从某个相邻位置出发，能够搜索到子串 word[k + 1]，则返回 true，否则返回 false；

更新行列号可以通过{上、下、左、右}，行列号不能越界，使用一个网格数组维护使用状态：

        // 更新行列号
        for (auto & d : directions) {
            int r = i + d[0];
            int c = j + d[1];
            // 行列号不能越界
            if (r >= 0 && r < board.size() && c >= 0 && c < board[0].size()) {
                // 当前格子没有被使用
                if (!visited[r][c]) {
                    bool flag = dfs(board, word, visited, r, c, k +1);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }

private:
        int directions[4][2] = {
            // right
            {0, 1},
            // left
            {0, -1},
            // down
            {1, 0},
            // up
            {-1, 0}
        };

完整代码：

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int row = board.size();
        if (0 == row) {
            return false;
        }
        int column = board[0].size();
        if (0 == column) {
            return false;
        }
        std::vector<std::vector<int>> visited(row, std::vector<int>(column));

        for (int i  = 0; i < row; ++i) {
            for (int j = 0; j < column; ++j) {
                bool flag = dfs(board, word, visited, i, j, 0);
                if (flag) {
                    return true;
                }
            }
        }

        return false;
    }

private:
    bool dfs(std::vector<std::vector<char>>& board, std::string word, 
        std::vector<std::vector<int>>& visited, int i, int j, int k) {
        if (board[i][j] != word[k]) {
            return false;
        } else if (k == word.size() - 1) {
            return true;
        }
        visited[i][j] = true;

        bool result = false;
        for (auto & d : directions) {
            int r = i + d[0];
            int c = j + d[1];
            if (r >= 0 && r < board.size() && c >= 0 && c < board[0].size()) {
                if (!visited[r][c]) {
                    bool flag = dfs(board, word, visited, r, c, k +1);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;

        return result;
    }

private:
        int directions[4][2] = {
            // right
            {0, 1},
            // left
            {0, -1},
            // down
            {1, 0},
            // up
            {-1, 0}
        };
};

文章来源地址https://www.toymoban.com/news/detail-801035.html

到了这里，关于力扣79. 单词搜索的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！