79. Word Search

class Solution:
    def dfs(self, word, board, x, y, visited):
        if board[x][y] != word[0]:
            return False

        if not word[1:]:
            return True

        dx = [0, -1, 0, 1]
        dy = [-1, 0, 1, 0]

        for i in range(4):
            rx, ry = x + dx[i], y + dy[i]
            if rx < 0 or ry < 0 or rx > len(board) - 1 or ry > len(board[0]) - 1:
                continue
            elif [rx, ry] in visited:
                continue
            else:
                visited.append([x, y])
                res = self.dfs(word[1:], board, rx, ry, visited)
                if res is True:
                    return res
                else:
                    visited.pop()

        return False



    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        if not board or not board[0]:
            return False

        m = len(board)
        n = len(board[0])

        for i in range(m):
            for j in range(n):
                res = self.dfs(word, board, i, j, [])
                if res is True:
                    return res

        return False