https://leetcode.com/problems/word-search/description/

word-search.py

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        return any(char == word[0] and self.search(board, word, x, y, set())
                   for y, row in enumerate(board) for x, char in enumerate(row))

    def search(self, board, word, x, y, visited):
        if not word:
            return True
        if (not (0 <= x < len(board[0])) or
            not (0 <= y < len(board)) or
            word[0] != board[y][x]):
            return False
        if len(word) == 1:
            return True

        visited.add((x, y))
        for dx, dy in [(0,1), (1,0), (0,-1), (-1,0)]:
            if ((x + dx, y + dy) not in visited and
                self.search(board, word[1:], x + dx, y + dy, visited)):
                return True
        visited.discard((x, y))
        return False