# Leetcode 79

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i,j,wordIndex, used):
            if wordIndex is len(word):
                return True
            if i<0 or j<0 or i>=len(board) or j>= len(board[0]) or (i, j) in used or board[i][j][0] != word[wordIndex]:
                return False
            used[(i, j)]=True
            ans = dfs(i+1,j,wordIndex+1,used) or dfs(i,j+1,wordIndex+1,used) or dfs(i-1,j,wordIndex+1,used) or dfs(i,j-1,wordIndex+1,used)
            del used[(i,j)]
            return ans


        ch = {}
        for i in range(len(board)):
            for j in range(len(board[0])):
                ch[board[i][j][0]] = True
        for c in word:
            if c not in ch:
                return False
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i,j,0,{}):
                    return True
        return False