class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if len(word) == 0: return True
if len(board) == 0: return False
for r in range(len(board)):
for c in range(len(board[0])):
if board[r][c] == word[0]:
if self.dfs(board, r, c, 0, word):
return True
return False
def dfs(self, board, r, c, idx, word):
if idx == len(word): return True
if r<0 or r>=len(board) or c<0 or c>=len(board[0]) or board[r][c]!=word[idx]:
return False
ch = board[r][c]
board[r][c] = '#'
res = self.dfs(board, r-1,c,idx+1,word) or self.dfs(board, r+1, c, idx+1, word) \
or self.dfs(board, r, c-1, idx+1, word) or self.dfs(board, r, c+1, idx+1, word)
board[r][c] = ch
return res