Keshawn_lu's Blog

Leetcode 79. 单词搜索

字数统计: 494阅读时长: 2 min
2020/09/13 Share

题目简介:

给定一个二维网格和一个单词,找出该单词是否存在于网格中。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

1
2
3
4
5
6
7
8
9
10
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

提示:

  • boardword 中只包含大写和小写英文字母。
  • 1 <= board.length <= 200
  • 1 <= board[i].length <= 200
  • 1 <= word.length <= 10^3

思路:

深搜,dfs()参数中定义一个count来说明目前有几个字符寻找成功,当count == word.size()时,说明搜索单词成功,返回true

为了防止重复使用,定义一个visit数组。

tip:

  • 注意二维数组的初始化。

代码如下:

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
class Solution {
public:

int dirx[4] = {0, 1, 0, -1};
int diry[4] = {-1, 0, 1, 0};

vector<vector<bool>> visit = vector<vector<bool>>(200, vector<bool>(200));

bool dfs(vector<vector<char>>& board, string& word, int count, int i, int j){

if(count == word.size())
return true;

for(int k = 0; k < 4; k++){

int x = j + dirx[k];
int y = i + diry[k];

if(x >= 0 && x < board[0].size() && y >= 0 && y < board.size()){

if(board[y][x] == word[count] && !visit[y][x]){

visit[y][x] = true;

if(dfs(board, word, count + 1, y, x))
return true;

visit[y][x] = false; //回溯
}
}
}

return false;
}

bool exist(vector<vector<char>>& board, string word) {

for(int i = 0; i < board.size(); i++){

for(int j = 0; j < board[i].size(); j++){

if(board[i][j] == word[0]){ //先去找第一个

visit[i][j] = true;
if(dfs(board, word, 1, i, j))
return true;
visit[i][j] = false;
}
}
}

return false;

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: