https://leetcode.com/problems/word-search/
- 通过修改访问标记的方式回溯
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
m = len(board)
n = len(board[0])
for i in range(m):
for j in range(n):
if self.dfs(i, j, 0, board, word):
return True
return False
def dfs(self, x, y, k, board, word):
if k == len(word):
return True
if x < 0 or x >= len(board) or y < 0 or y >= len(board[0]) or board[x][y] != word[k]:
return False
mem = board[x][y]
board[x][y] = '*'
res = self.dfs(x+1, y, k+1, board, word) or self.dfs(x, y+1, k+1, board, word) or self.dfs(x-1, y, k+1, board, word) or self.dfs(x, y-1, k+1, board, word)
board[x][y] = mem
return res时间复杂度：O(mn4^word)
空间复杂度：O(4^word)