Leetcode-79 Word Search

描述

在给定的 2D 平面 board 中搜索单词 word,可以在垂直相邻和水平相邻方向进行深度搜索,如果找到返回 True,否则返回 False。

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

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

测试用例

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

# Case 0: word is an empty string, word = '', return false
# Case 1: genaral case - word = "ABFE", return true
# Case 2: take backtracking under advisement, word = "AEFBCAFE", return true.
# Case 3: word = "ADEF", return false

分析

这是一个经典的 DFS 问题,对于一个坐标 (x, y) 可以往四个方向进行搜索,分别是 (x+1, y), (x-1, y), (x, y+1), (x, y-1)。四个方向只要有一个方向搜索成功即可,搜索成功的条件是搜索深度 d == len(word)-1。而搜素失败的原因有很多:

  1. (x, y) 出界;
  2. (x, y) 已经使用过(题目要求每个坐标只能使用一次);
  3. 当前的 (x, y) 对应的值和 word[d] 不相等。

根据以上分析,构造 dfs 函数需要的参数有 x, y 和 d,其中 d 表示搜索的深度。此外,还需要一个保存搜索过的坐标的辅助变量,这个变量可以放在全局。考虑搜索失败的情况,代码如下:

1
2
3
4
5
6
7
8
9
visited = set()
def dfs(x, y, d):
if out_of_bound(x, y):
return False
if (x, y) in visited:
return False
if board[x][y] != word[d]:
return False
# TODO

如果当前坐标 (x, y) 满足条件 board[x][y] == word[d]d == len(word) - 1 则搜索成功,代码如下

1
2
3
4
5
6
7
8
9
10
visited = set()
def dfs(x, y, d):
if out_of_bound(x, y):
return False
if (x, y) in visited:
return False
if board[x][y] != word[d]:
return False
if d == len(word) - 1:
return True

否则继续往当前坐标的四个方向深入搜索,同时将当前坐标加入到 visited 中,表示当前坐标已经访问过,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
visited = set()
def dfs(x, y, d):
if out_of_bound(x, y):
return False
if (x, y) in visited:
return False
if board[x][y] != word[d]:
return False
if d == len(word) - 1:
return True

# continue dfs
visited.add((x,y))
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
found = False
for i in range(4):
new_x = x + dx
new_y = y + dy
found = found or dfs(new_x, new_y, d+1)

return found

如上,代码基本结构已经完成,大部分测试已经通过。但是, 考虑具有回溯情况的 Case 2 ,以上代码会失。这是因为如果坐标 (x,y) 的某个方向深入搜索多个步骤后失败,最终还会回到 (x, y) 上进行下一个方向的尝试,可是在进行下一个方向搜索时,上次的失败搜索并没有释放搜索过的坐标,导致有些坐标在本次搜索不能被访问,最终搜索失败。 所以,对于当前坐标的搜索,如果四个方向都搜索失败,则需要释放当前的 (x, y),即 回溯。如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
visited = set()
def dfs(x, y, d):
if out_of_bound(x, y):
return False
if (x, y) in visited:
return False
if board[x][y] != word[d]:
return False
if d == len(word) - 1:
return True

# continue dfs
visited.add((x,y))
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
found = False
for i in range(4):
new_x = x + dx
new_y = y + dy
found = found or dfs(new_x, new_y, d+1)
if not found:
visited.remove((x, y))
return found

代码实现

根据如上分析,代码实现如下(实现使用 used 数组保存访问过的坐标,和用集合 visited 功能一致):

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
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if not board or not word:
return False
m, n = len(board), len(board[0])
used = [[False] * n for _ in range(m)]
def dfs(x, y, pos):
# x, y out of bound
if x < 0 or x >= m or y < 0 or y >= n:
return False
# word[pos] not equals to board[x][y]
if word[pos] != board[x][y]:
return False
# (x, y) already used
if used[x][y]:
return False
# pos == len(word)-1
if pos == len(word) - 1:
return True

used[x][y] = True
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

found = False
for i in range(4):
new_x = x + dx[i]
new_y = y + dy[i]
found = found or dfs(new_x, new_y, pos+1)
# backtrack
if not found:
used[x][y] = False
return found

for i in range(m):
for j in range(n):
if dfs(i, j, 0):
return True
return False

改进:

如上代码使用额外空间来记录访问过的坐标,以避免重复访问,有个技巧可以使用 O(1) 的空间记录访问过的节点。我们只需要用一个特殊符号如 “#” 将访问过的坐标值替换,勾勒出访问路径,并在当前坐标搜索完成后将原来的值替换回来即可。如下:

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
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if not board or not word:
return False
m, n = len(board), len(board[0])
def dfs(x, y, pos):
# x, y out of bound
if x < 0 or x >= m or y < 0 or y >= n:
return False
# word[pos] not equals to board[x][y]
if word[pos] != board[x][y]:
return False
# pos == len(word)-1
if pos == len(word) - 1:
return True

orignal = board[x][y]
board[x][y] = "#"
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

found = False
for i in range(4):
new_x = x + dx[i]
new_y = y + dy[i]
found = found or dfs(new_x, new_y, pos+1)
# backtrack
board[x][y] = orignal
return found

for i in range(m):
for j in range(n):
if dfs(i, j, 0):
return True
return False

本文标题:Leetcode-79 Word Search

文章作者:Syncher

发布时间:2019年11月11日 - 22:11

最后更新:2019年11月11日 - 23:11

原始链接:https://0x400.com/2019-11-11-lc-79-word-search.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。