leetcode: 79. Word Search

# Given a 2D board and a word, find if the word exists in the grid.
#
# The word can be constructed from letters of sequentially adjacent cell,
# where "adjacent" cells are those horizontally or vertically neighboring.
# The same letter cell may not be used more than once.
#
# For example,
# Given board =
# [
#   ['A','B','C','E'],
#   ['S','F','C','S'],
#   ['A','D','E','E']
# ]
#
# word = "ABCCED", -> returns true,
# word = "SEE", -> returns true,
# word = "ABCB", -> returns false.

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