LeetCode79 单词搜索

链接: https://leetcode-cn.com/problems/word-search/description/

题意

给定一个字母矩阵,所有的字母都与上下左右四个方向上的字母相连。给定一个字符串,求字符串能不能在字母矩阵中寻找到。

解法

又是一道比较明显的要用到回溯的题目,题目本身不难
这里还是练习一种新的回溯的写法
visit置位放在递归和回溯的前后
用一个引用变量flag来标记是否找到结果
要注意访问visit数组时的细节,下标是乘以列数,之前就在这个位置翻了车 查了很久才找出来
用一个map数组来提前确定矩阵中是否存在单词中需要的字母

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
class Solution {
public:
void dfs(int pos, string word, int x, int y, vector<vector<char>>& board, vector<int>& visit, bool& find) {
int m = board.size(), n = board[0].size();
if (x < 0 || x >= m || y < 0 || y >= n) {
return;
}
if (visit[x * n + y] || find || board[x][y] != word[pos]) {
return;
}
if (pos == word.size() - 1) {
find = true;
return;
}
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
visit[x * n + y] = 1;
for (int i = 0; i < 4; i++) {
int xx = x + dx[i], yy = y + dy[i];
dfs(pos + 1, word, xx, yy, board, visit, find);
}
visit[x * n + y] = 0;
}

bool exist(vector<vector<char>>& board, string word) {
int m = board.size(), n = board[0].size();
map<char, int> chars;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
chars[board[i][j]] = 1;
}
}
for (char ch: word) {
if (chars[ch] == 0) {
return false;
}
}
vector<int> visit(m * n);
bool find = false;
for(int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dfs(0, word, i, j, board, visit, find);
}
}
return find;
}
};