class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        self.board = board
        self.m = len(board)
        self.n = len(board[0])
        words = set(words)
        found = []

        for row in range(len(board)):
            for col in range(len(board[0])):
                for word in words:
                    if word[0] == board[row][col] and word not in found:
                        if self.backtrack(row,col,word,0):
                            found.append(word)  
        return found
        
    
    def backtrack(self,x,y,word,count):
        if x < 0 or y < 0 or x >= self.m or y >= self.n or self.board[x][y] == "#":
            return False
        if word[count] != self.board[x][y]:
            return False
        if count == len(word)-1:
            return True
        
        
        
        temp = self.board[x][y]
        self.board[x][y] = "#"
        
        if self.backtrack(x+1,y,word,count+1) or self.backtrack(x-1,y,word,count+1) or self.backtrack(x,y+1,word,count+1) or self.backtrack(x,y-1,word,count+1):
            self.board[x][y] = temp
            return True
        
        self.board[x][y] = temp
        return False