We could use DFS to search for the correct answer. While doing the DFS process, once we have used a letter, we need to mark it to None to not use it for more than once.
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if not board or not board[0]:
return word == ''
m, n = len(board), len(board[0])
for i in range(m):
for j in range(n):
if self._dfs(board, i, j, 0, word):
return True
return False
def _dfs(self, board, i, j, index, word):
m, n = len(board), len(board[0])
c = word[index]
if board[i][j] != word[index]:
return False
elif index + 1 == len(word):
return True
board[i][j] = None
for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if not 0 <= x < m or not 0 <= y < n:
continue
if self._dfs(board, x, y, index + 1, word):
return True
board[i][j] = c