class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:

        # get all valid letters in board
        valid_letters = set()
        for i in range(len(board)):
            for j in range(len(board[0])):
                valid_letters.add(board[i][j])

        def helper(board,i,j,idx,word):
            #base case
            if idx == len(word) - 1:
                return True


            neighbors=[(i-1,j),(i+1,j),(i,j+1),(i,j-1)]

            for x,y in neighbors:
                if x>=0 and x<len(board) and y>=0 and y<len(board[0]) and board[x][y]==word[idx+1]:
                    prev=board[x][y]
                    board[x][y]='.'
                    if helper(board,x,y,idx+1,word):
                        board[x][y]=prev
                        return True
                    board[x][y]=prev
            return False

        array=[]
        for word in words:
             # check if word contains any invalid letters
            valid_word = True
            for char in word:
                if char not in valid_letters:
                    valid_word = False
            if valid_word == False:
                continue

            found = False
            for i in range(len(board)):
                if found: # break the loop if the word has been found
                    break
                for j in range(len(board[0])):
                    if found:
                        break
                    if board[i][j]==word[0]:
                        prev=board[i][j]
                        board[i][j]='.'
                        if helper(board,i,j,0,word):
                            found = True
                        board[i][j]=prev
            if found:
                array.append(word);
        return array