力扣79. 单词搜索

发布时间:2024年01月18日

回溯

  • 思路:
    • 定义函数 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://blog.csdn.net/N_BenBird/article/details/135662907
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。