class Solution():
def exist(self, board, word):
visited = [[False for __ in range(len(board[0]))] for _ in range(len(board))]
for i in range(len(board)):
for j in range(len(board[0])):
if self.existRecu(board, word, 0, i, j, visited):
return True
return False
def existRecu(self, board, word, cur, i, j, visited):
if cur == len(word):
return True
if not (0 <= i < len(board) and 0 <= j < len(board[0])) or not (not visited[i][j] and board[i][j] == word[cur]):
return False
visited[i][j] = True
res = self.existRecu(board, word, cur + 1, i + 1, j, visited) or \
self.existRecu(board, word, cur + 1, i - 1, j, visited) or \
self.existRecu(board, word, cur + 1, i, j + 1, visited) or \
self.existRecu(board, word, cur + 1, i, j - 1, visited)
visited[i][j] = False
return res
if __name__ == "__main__":
board = [
"ABCE",
"SFCS",
"ADEE"
]
assert Solution().exist(board, "ABCCED") == True
assert Solution().exist(board, "SFCS") == True
assert Solution().exist(board, "ABCB") == False