[leetcode]Word Search II

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        if len(board) == 0 or len(board[0]) == 0:
            return []
        
        m = len(board)
        n = len(board[0])
        
        prefixSet = set()
        for word in words:
            for i in range(len(word)):
                prefixSet.add(word[ : i + 1])
                
        result = []
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                visited = [[False] * n for k in range(m)]
                self.backtrace(board, visited, words, prefixSet, ‘‘, i, j, 0, result)
                
        result = sorted(result)
        return result
                
    def backtrace(self, board, visited, words, prefixSet, word, i, j, step, result):
        m = len(board)
        n = len(board[0])
        
        visited[i][j] = True
        word = word + board[i][j]
        
        if word in prefixSet:
            if word in words and word not in result:
                result.append(word)
            for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                if i + dx < 0 or i + dx >= m or j + dy < 0 or j + dy >= n:
                    continue
                if not visited[i + dx][j + dy]:
                    self.backtrace(board, visited, words, prefixSet, word, i + dx, j + dy, step + 1, result)
                    
        visited[i][j] = False