Solutions

# Recursion with backtracking: for each cell, we check if it matches the current character in the word. If it does, we mark it as visited and recursively check its neighbors for the next character in the word.
# backtracking

# Time: O(m*n*4^l) where m and n are the dimensions of the board, and l is the length of the word. In the worst case, we might have to explore all paths in the board for each character in the word.
# Space: O(l) for the recursion stack, where l is the length of the word. Additionally, we use O(l) space for the path set in the worst case, if the word is found along a path that covers l cells in the board.
def exist(board: list[list[str]], word: str) -> bool:
    path = set()

    def dfs(r: int, c: int, i: int):
        if i == len(word):
            return True

        if r >= len(board) or c >= len(board[0]) or r < 0 or c < 0 or \
                board[r][c] != word[i] or \
                (r,c) in path:
            return False

        path.add((r,c))
        res = (dfs(r + 1, c, i+1) or \
                dfs(r, c + 1, i+1) or \
                dfs(r -1, c, i+1) or \
                dfs(r, c -1, i+1))
        path.remove((r,c))
        return res

    for r in range(len(board)):
        for c in range(len(board[0])):
            if dfs(r, c, 0):
                return True
    return False