Word Search

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board or not board[0]:
            return False
        row_len = len(board)
        col_len = len(board[0])
        for i in range(row_len):
            for j in range(col_len):
                if board[i][j] == word[0]:
                    if self.dfs(board, (i, j), word):
                        return True
        return False

    def dfs(self, board, start, word):
        my_stack = []
        visited = set()
        my_stack.append((start[0], start[1], 0, False))
        word_len = len(word)
        row_len = len(board)
        col_len = len(board[0])
        while my_stack:
            i, j, level, backtrack = my_stack.pop()
            if backtrack:
                visited.remove((i, j))
                continue

            visited.add((i, j))
            my_stack.append((i, j, 0, True))
            if level == word_len - 1 and board[i][j] == word[level]:
                return True

            for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                if 0 <= x < row_len and 0 <= y < col_len and (x, y) not in visited and board[x][y] == word[
                    level + 1]:
                    my_stack.append((x, y, level + 1, False))

        return False