79. Word Search (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        def dfs(i, j, seen, cur):
            if not self.result:
                if board[i][j] == cur[0]:
                    if len(cur) == 1:
                        self.result = True
                        return
                    for dx, dy in (1, 0), (0, 1), (-1, 0), (0, -1):
                        x, y = i + dx, j + dy
                        if 0 <= x < m and 0 <= y < n:
                            if (x, y) not in seen:
                                dfs(x, y, seen | {(i, j)}, cur[1 : ])
        for i in range(m):
            for j in range(n):
                self.result = False
                dfs(i, j, set(), word)
                if self.result:
                    return True
        return False