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
| class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
visited = [[False for j in range(len(board[0]))] for i in range(len(board))]
for i in range(len(board)):
for j in range(len(board[0])):
if self.existRecu(board, word, 0, i, j, visited):
return True
return False
def existRecu(self, board, word, cur, i, j, visited):
if cur == len(word): # 如果到单词长度，结束。
return True
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or visited[i][j] or board[i][j] != word[cur]:
return False # 越界或者是当前字母不等于word中对应位置字母
# 如果到这说明对应位置有，继续从此位置遍历四个方向
visited[i][j] = True
result = self.existRecu(board, word, cur + 1, i + 1, j, visited) or\
self.existRecu(board, word, cur + 1, i - 1, j, visited) or\
self.existRecu(board, word, cur + 1, i, j + 1, visited) or\
self.existRecu(board, word, cur + 1, i, j - 1, visited)
visited[i][j] = False
return result
|