Python sol by DFS [w/ Comment ]
Python sol by DFS with 4-connected path\n\n---\n\nImplementation by DFS:\n\n\nclass Solution:\n    def exist(self, board: List[List[str]], word: str) -> bool:\n
Python sol by DFS with 4-connected path\n\n---\n\n**Implementation** by DFS:\n\n```\nclass Solution:\n    def exist(self, board: List[List[str]], word: str) -> bool:\n        \n        if not board: \n            \n            # Quick response for empty board\n            return False\n        \n        h, w = len(board), len(board[0])\n      \n        # ------------------------------------------------------\n    \n        def dfs_search(idx: int, x: int, y: int) -> bool:\n            \n            if x < 0 or x == w or y < 0 or y == h or word[idx] != board[y][x]:\n                # Reject if out of boundary, or current grid cannot match the character word[idx]\n                return False\n\n            if idx == len(word) - 1: \n                # Accept when we match all characters of word during DFS\n                return True\n\n            cur = board[y][x]\n            \n            # mark as \'#\' to avoid repeated traversal\n            board[y][x] = \'#\'\n            \n            # visit next four neighbor grids\n            found = dfs_search(idx + 1, x + 1, y) or dfs_search(idx + 1, x - 1, y) or dfs_search(idx + 1, x, y + 1) or dfs_search(idx + 1, x, y - 1)\n            \n            # recover original grid character after DFS is completed\n            board[y][x] = cur\n            \n            return found\n\n        # ------------------------------------------------------\n        \n        return any(dfs_search(0, x, y) for y in range(h) for x in range(w))      \n```
['Depth-First Search', 'Recursion', 'Python', 'Python3']