单词搜索

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param board string字符串一维数组 
# @param word string字符串 
# @return bool布尔型
#
class Solution:
    def exist(self , board: List[str], word: str) -> bool:
        # write code here
        visited = [[False for i in range(len(board[0]))] for j in range(len(board))]

        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0]:
                    found  = self.traverse(board, visited, i,j, word, 0)

                    if found:
                        return True
        return False


    def traverse(self, board, visited, x, y, word, now_count):
        if board[x][y] == word[now_count]:
            now_count += 1
        else:
            return False

        if now_count == len(word):
            return True

        visited[x][y] = True
        found = False
        if x - 1 >= 0:
            if not visited[x-1][y]:
                found |= self.traverse(board, visited, x-1, y, word, now_count)

        if x+1 < len(board):
            if not visited[x+1][y]:
                found |= self.traverse(board, visited, x+1, y, word, now_count)

        if y - 1 >= 0:
            if not visited[x][y-1]:
                found |= self.traverse(board, visited, x, y-1, word, now_count)

        if y+1 < len(board[0]):
            if not visited[x][y+1]:
                found |= self.traverse(board, visited, x, y+1, word, now_count)
        visited[x][y] = False

        return found