class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
rows = len(board)
cols = len(board[0])
directions = [(1,0),(-1,0),(0,1),(0,-1)]
def backtrack(r, c, word):
if len(word) == 0:
return True
if 0 <= r < rows and 0 <= c < cols and board[r][c] == word[0]:
board[r][c] = '#'
for dr, dc in directions:
if backtrack(r+dr, c+dc, word[1:]):
return True
board[r][c] = word[0]
return False
for r in range(rows):
for c in range(cols):
if backtrack(r, c, word):
return True
return False