给出一个二维字符矩阵，问其中是否存在给定的单词（每次向上下左右四个方向寻找），简单DFS。不过一开始把DFS函数单独写，一直TLE，写在exist函数内就可以AC
1 #79
2 #Runtime: 4858 ms
3 #Memory Usage: 14 MB
4
5 class Solution(object):
6
7 def exist(self, board, word):
8 """
9 :type board: List[List[str]]
10 :type word: str
11 :rtype: bool
12 """
13 d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
14 def DFS(x, y, vis, l):
15 if l == len(word) - 1:
16 return True
17 for dx, dy in d:
18 tx = x + dx
19 ty = y + dy
20 if 0 <= tx < len(board) and 0 <= ty < len(board[0]) and word[l + 1] == board[tx][ty] and (tx, ty) not in vis:
21 vis.add((tx, ty))
22 if DFS(tx, ty, vis, l + 1):
23 return True
24 vis.remove((tx, ty))
25 return False
26 for i in range(len(board)):
27 for j in range(len(board[0])):
28 if board[i][j] == word[0]:
29 if DFS(i, j, {(i, j)}, 0):
30 return True
31 return False