1
class Solution:
2
    def exist(self, board: List[List[str]], word: str) -> bool:
3
        m = len(board)
4
        n = len(board[0])
5

6
        marked = set()  # visited by the dfs
7

8
        def dfs(cell: Tuple[int, int], wp: int) -> bool:
9
            i = cell[0]
10
            j = cell[1]
11

12
            if wp == len(word):
13
                return True
14

15
            # Get appropriate neighbours and perform dfs on them
16
            # When going on dfs, we mark certain cells, we should remove #
17
            # them from the marked list after we return from the dfs
18
            marked.add((i, j))
19
            neibs = [(i - 1, j), (i, j - 1), (i + 1, j), (i, j + 1)]
20
            for x, y in neibs:
21
                if (
22
                    x < 0
23
                    or y < 0
24
                    or x >= m
25
                    or y >= n
26
                    or (x, y) in marked
27
                    or board[x][y] != word[wp]
28
                ):
29
                    continue
30

31
                if dfs((x, y), wp + 1):
32
                    return True
33

34
            marked.remove((i, j))
35
            return False
36

37
        for i in range(m):
38
            for j in range(n):
39
                if board[i][j] == word[0]:
40
                    if dfs((i, j), 1):
41
                        return True
42

43
        return False