Leetcode 79. 单词搜索_leetcode79c++

1、问题分析

题目链接：https://leetcode-cn.com/problems/word-search/
  本质上就是一个深搜问题。代码我已经进行了详细的注释，理解应该没有问题，读者可以作为参考，如果看不懂(可以多看几遍)，欢迎留言哦！我看到会解答一下。

2、问题解决

  笔者以C++方式解决。

#include "iostream"

using namespace std;

#include "algorithm"
#include "vector"
#include "queue"
#include "set"
#include "map"
#include "string"
#include "stack"

class Solution {
private:
    // 标记某个节点是否访问过
    vector<vector<int>> vis;
    // 存储字符串第一个字符在二维网格中的位置
    // 例如：示例中 word = "ABCCED"，则 positions={{0,0}，{2,0}}
    vector<vector<int>> positions;

    // 模拟节点的上下移动
    vector<int> X = { 0, 0, 1, -1 };
    vector<int> Y = { 1, -1, 0, 0 };

public:
    bool exist(vector<vector<char>> &board, string word) {
        // 网格为空，说明单词不存在网格中
        if (board.empty()) {
            return false;
        }

        return dealChen(board, word);
    }

    /**
     * 初始化访问数组
     * @param board
     */
    void init(vector<vector<char>> &board) {
        // 首先一定要将 数组清空，否则直接 resize 没有达到真正初始化的目的
        vis.clear();
        // 然后一定要 resize ，因为 clear() 之后 vis 数组大小就会变成 0
        vis.resize(board.size());
        for (int i = 0; i < board.size(); ++i) {
            vis[i].resize(board[i].size());
        }
    }

    /**
     * 查找二维网格中是否存在指定单词
     * @param board
     * @param word
     * @return
     */
    bool dealChen(vector<vector<char>> &board, string word) {
        // 由于题目中给出 指定单词 肯定不为空，所以 word[0] 不会越界
        // 否则需要特殊处理。将字符串第一个字符在二维网格中的位置存储到数组中
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[i].size(); ++j) {
                // 找到第一个字符
                if (board[i][j] == word[0]) {
                    vector<int> pos;
                    // (i,j)代表节点位置
                    pos.push_back(i);
                    pos.push_back(j);
                    positions.push_back(pos);
                }
            }
        }

        // 没有第一个字符，说明肯定不存在该单词，美滋滋，直接返回 false
        if (positions.empty()) {
            return false;
        }

        // 依次从第一个节点遍历二维网格，查找是否存在指定单词
        for (int k = 0; k < positions.size(); ++k) {
            // 每次遍历都要初始化访问数组，可能之前不可以的路径，限制就可以了
            init(board);

            // 获取开始节点位置
            int x = positions[k][0];
            int y = positions[k][1];
            // 设置该节点已经访问过
            vis[x][y] = 1;

            // 如果指定单词就一个字符，那只要判断和我们存在的第一个是否相等即可
            // 美滋滋，快速获取结果
            if (word.length() == 1) {
                return board[x][y] == word[0];
            }

            // 否则的话从该节点开始深搜
            bool b = dfs(board, word, x, y, 1);
            // 无论那一次，深搜到，说明单词存在网格中
            if (b) {
                return b;
            }
        }

        // 如果所有的dfs都没有搜索到，说明该单词不存在于网格中
        return false;
    }

    /**
     * 从节点 (x,y) 开始，在二维网格 board 中查找 是否存在某个位置的值和
     * 指定单词 word 的第 index 个位置的值相等
     * @param board
     * @param word
     * @param x
     * @param y
     * @param index
     * @return
     */
    bool dfs(vector<vector<char>> &board, string word, int x, int y, int index) {

        // 越界肯定不等
        if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size()) {
            return false;
        }

        // 单词索引合法
        if (index < word.length()) {
            // 模拟上下左右四次移动
            for (int j = 0; j < 4; ++j) {
                int newX = x + X[j];
                int newY = y + Y[j];
                // 新坐标要合法
                if (newX >= 0 && newX < board.size() && newY >= 0 && newY < board[0].size()) {
                    // 如果该坐标没有访问过
                    if (vis[newX][newY] == 0) {
                        // 如果新的值正好等于 指定单词 word 的第 index 个位置的值
                        if (board[newX][newY] == word[index]) {
                            // 正好遍历到单词结尾了
                            if (index == (word.length() - 1)) {
                                // 说明找到了，尼玛，好费劲啊
                                return true;
                            }
                            // 如果还没有找到，那就先标志该节点已经被访问过了
                            vis[newX][newY] = 1;
                            // 继续从新节点开始 深搜，是否存在值和单词的第 index + 1 的值相等
                            bool b = dfs(board, word, newX, newY, index + 1);
                            // 如果层层搜索，搜索到了，那就直接返回 true
                            if (b) {
                                return true;
                            }
                            else {
                                // 如果经过该节点无法搜索到，那就将该节点标记成未访问
                                vis[newX][newY] = 0;
                            }
                        }
                    }
                }
            }
        }

        // 经过上下左右搜索都没有找到，说明该单词不存在于网格中
        return false;
    }
};

int main() {
        vector<vector<char>> board = {
                { 'A', 'B', 'C', 'E' },
                { 'S', 'F', 'C', 'S' },
                { 'A', 'D', 'E', 'E' }
        };
//    vector<vector<char>> board = { { 'C', 'A', 'A' },
//                                   { 'A', 'A', 'A' },
//                                   { 'B', 'C', 'D' } };

    //    vector<vector<char>> board = {
    //            { 'A'},
    //    };

    string word = "AAB";

    Solution *pSolution = new Solution;
    bool b = pSolution->exist(board, word);
    cout << b << endl;
    system("pause");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183

运行结果

有点菜，有时间再优化一下。

3、总结

  难得有时间刷一波LeetCode, 这次做一个系统的记录，等以后复习的时候可以有章可循，同时也期待各位读者给出的建议。算法真的是一个照妖镜，原来感觉自己也还行吧，但是算法分分钟教你做人。前人栽树，后人乘凉。在学习算法的过程中，看了前辈的成果，受益匪浅。
感谢各位前辈的辛勤付出，让我们少走了很多的弯路！
哪怕只有一个人从我的博客受益，我也知足了。
点个赞再走呗！欢迎留言哦！