Leetcode 79 单词搜索
# Leetcode 79 单词搜索
# 1. 题目
# 79. 单词搜索 (opens new window)
给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
提示:
board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3
1
2
3
4
2
3
4
# 2. 代码
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int n = board.size();
int m = board[0].size();
for(int i = 0; i<n; ++i){
for(int j = 0; j<m; ++j){
if(board[i][j] == word[0] && dfs(i, j, board, word, 0)){
return true;
}
}
}
return false;
}
private:
bool dfs(int x, int y, vector<vector<char>>& board, string& word, int index){
int n = board.size();
int m = board[0].size();
if(x<0 || x>=n || y<0 || y>=m || board[x][y] != word[index]){
return false;
}
if(index == word.size() - 1){
return true;
}
char c = board[x][y];
board[x][y] = '\0';
if(dfs(x + 1, y, board, word, index + 1)
|| dfs(x - 1, y, board, word, index + 1)
|| dfs(x, y + 1, board, word, index + 1)
|| dfs(x, y - 1, board, word, index + 1)){
return true;
}
board[x][y] = c;
return false;
}
};
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
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
# 3. 思路
感觉思路很简单,这里贴一下修改过程。本来交上是60ms 很慢,后面改成了24ms。
60ms优化到24ms的心得:
- 去掉循环,直接四个方向用||连接判断
- 不用used,在原board上修改(当然这样不一定规范
- 结束条件放到检查边界后面,因为结束条件true的次数很少,放前面开销大
- 使用if(dfs()) return true;这种模式,可以节约flag变量
编辑 (opens new window)
上次更新: 2023/03/02, 12:43:17