79. 单词搜索(Medium)
# 题目描述
给定一个二维网格和一个单词,找出该单词是否存在于网格中。
# 样例
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
2
3
4
5
6
7
8
9
10
# 题解
本题是常见的 图 的搜索问题,使用深度搜索 。因为我们需要退回上一个节点状态,所以需要使用回溯法,记录和恢复状态。使用 visited 数组标记节点是否走过。
# Python示例
def dfs(board, word, visited, r, c):
if not word: # 找到
return True
direction = [-1, 0, 1, 0, -1]
for d in range(4):
i = r + direction[d]
j = c + direction[d + 1]
if 0<= i < len(board) and \
0<= j < len(board[0]) and \
board[i][j] == word[0] and \
not visited[i][j]: # 未访问过
visited[i][j] = 1
if dfs(board, word[1:], visited, i, j): return True # 剪枝:找到答案
visited[i][j] = 0
return False # 遍历完仍未找到
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == word[0]:
visited = [[0] * len(board[0]) for _ in range(len(board))]
visited[i][j] = 1
if dfs(board, word[1:], visited, i, j):
return True
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
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
同样,判断是否符合规则的代码可以放在 DFS 的开头,这样代码稍微变一下。
def dfs(board, word, visited, r, c):
if not word: # 找到
return True
if r < 0 or r >= len(board) or c < 0 or c >= len(board[0]) \
or visited[r][c] \
or board[r][c] != word[0]:
return False
direction = [-1, 0, 1, 0, -1]
visited[r][c] = 1
for d in range(4):
i = r + direction[d]
j = c + direction[d + 1]
if dfs(board, word[1:], visited, i, j):
return True # 剪枝:找到答案
visited[r][c] = 0
return False # 遍历完仍未找到
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
visited = [[0] * len(board[0]) for _ in range(len(board))]
for i in range(len(board)):
for j in range(len(board[0])):
if dfs(board, word, visited, i, j):
return True
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
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
# Go 示例
func dfs(board [][]byte, word string, visited [][]bool, r, c int) bool {
if len(word) == 0 {
return true
}
if r < 0 || r >= len(board) || c < 0 || c >= len(board[0]) ||
board[r][c] != word[0] || visited[r][c] {
return false
}
visited[r][c] = true
directions := []int {-1, 0, 1, 0, -1}
for d := 0; d < 4; d ++ {
x := r + directions[d]
y := c + directions[d + 1]
if dfs(board, word[1:], visited, x, y) {
return true
}
}
visited[r][c] = false
return false
}
func exist(board [][]byte, word string) bool {
n, m := len(board), len(board[0])
visited := make([][]bool, n)
for i := range visited {
visited[i] = make([]bool, m)
}
for i := 0; i < n; i ++ {
for j := 0; j < m; j ++ {
if dfs(board, word, visited, i, j) {
return true
}
}
}
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
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
编辑 (opens new window)
上次更新: 2022/10/25, 02:40:54