Leetcode 79:单词搜索(最详细的解法!!!)

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

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

示例:

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.

解题思路

这实际上还是一个回溯法解决的问题。例如,对于word = 'ABCCED',我们从第一个元素开始,首先匹配到A,然后向后面寻找。我们规定好寻找的顺序为::arrow_up:,:arrow_right:,:arrow_down:,:arrow_left:。我们接着找B,上面越界,右边找到了。我们接着找C,上面越界,右边找到了。我们接着找C,上面越界了,右边不对,下面找到了。接着找E,我们发现上面访问过,不再访问。接着向右查找,发现不匹配,接着向下查找,发现越界了,接着想做查找,OK!我们所有元素匹配成功。

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
class Solution:
def _searchWord(self, board, word, index, x, y, visited):
def inArea(x, y):
return 0 <= x < self.lx and 0 <= y < self.ly

d = [(-1, 0), (0, 1), (1, 0), (0, -1)]
if index + 1 == len(word):
return board[x][y] == word[index]

if board[x][y] == word[index]:
visited[x][y] = True
for i in range(4):
x_ = x + d[i][0]
y_ = y + d[i][1]
if inArea(x_, y_) and not visited[x_][y_] and self._searchWord(board, word, index + 1, x_, y_, visited):
return True

visited[x][y] = False

return False

def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
visited = list()

for i in board:
t = list()
for _ in i:
t.append(False)

visited.append(t)

self.lx, self.ly = len(board), len(board[0])
for i, val in enumerate(board):
for j, _ in enumerate(val):
if self._searchWord(board, word, 0, i, j, visited):
return True

return False

我们对这样的问题有这样的一部优化处理,我们先统计wordboard的字符以及各字符的个数,比较这两者是不是一个包含的关系,也就是word <= board,如果不是,我们直接返回false。这种优化,对于返回bool类型的问题有一定的作用。

我们下面的写法没有使用visited,而是使用了临时的tmp,存储board[i][j]是否访问,如果访问过了,我们将board[i][j]='#'

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
import collections
class Solution:
def _exist(self, board, i, j, word, k):
if k == len(word):
return True

if i < 0 or i >= len(board) or j < 0 or j >= len(board[i]):
return False

if board[i][j] == word[k]:
temp = board[i][j]
board[i][j] = '#'
for d in range(4):
if self._exist(board, i + self.direct[d][0], j + self.direct[d][1], word, k + 1):
return True

board[i][j] = temp

return False

def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
if not board:
return False

board_c = collections.Counter([c for row in board for c in row])
word_c = collections.Counter(word)
for c in word_c:
if not c in word_c or word_c[c] > board_c[c]:
return False

r, c = len(board), len(board[0])
self.direct = [(-1, 0), (0, 1), (1, 0), (0, -1)]

for i in range(r):
for j in range(c):
if board[i][j] == word[0]:
if self._exist(board, i, j, word, 0):
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
39
40
41
42
43
44
45
46
47
class Solution:  
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
q = list()

lx, ly = len(board), len(board[0])
for r in range(lx):
for c in range(ly):
if board[r][c] == word[0]:
q.append((r, c))

def neighbors(board, r, c):
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
nbs = []
for d in directions:
nr = r + d[0]
nc = c + d[1]
if 0 <= nr < lx and 0 <= nc < ly:
nbs.append((nr, nc))
return nbs

for (r, c) in q:
visited = set()
stack = list()
stack.append((r, c, 0, False))
while stack:
cr, cc, i, bt = stack.pop()
if bt:
visited.remove((cr, cc))
continue

visited.add((cr, cc))
stack.append((cr, cc, i, True))
if i == (len(word) - 1):
return True

for nr, nc in neighbors(board, cr, cc):
if (nr, nc) in visited:
continue
if board[nr][nc] == word[i + 1]:
stack.append((nr, nc, i + 1, False))

return False

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!