My Python solution TLE, any idea to improve?


  • 0
    Z

    Similar idea as using Trie. Do DFS for each word, extend from prefix to whole string. If meets "fail", mark current prefix as "denied". Following words with this prefix is directly denied without doing DFS.

    def findWords(self, board, words):
        if not board or not board[0]: return []
        m, n = len(board), len(board[0])
        
        deny = set()
        
        def find(i, j, word):
            if not word or word in deny or i not in range(m) or j not in range(n) or board[i][j] != word[0]: 
                return False
            if len(word) == 1: 
                return True
            temp, board[i][j] = board[i][j], "#"
            ret = any((find(i+1, j, word[1:]), find(i-1, j, word[1:]), find(i, j+1, word[1:]), find(i, j-1, word[1:])))
            board[i][j] = temp
            return ret
        
        ret = []
        words = sorted(set(words)) # remove duplicates and guarantee prefix appear before target word
        for word in words:
            for idx in range(1, len(word)+1):
                if not any(find(i, j, word[:idx]) for i in range(m) for j in range(n)):
                    deny.add(word[:idx])
                    break
                elif idx == len(word):
                    ret.append(word)
        return ret

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.