Share my accepted python code (1580ms), how to speed up?


  • 0
    B
    class Solution:
        # @param start, a string
        # @param end, a string
        # @param dict, a set of string
        # @return a list of lists of string
        alphabets = "abcdefghijklmnopqrstuvwxyz"
    
        def findLadders(self, start, end, dict):
            if start == end: return [[start, end]]
    
            self.pathes = {}
            for word in list(dict):
                self.pathes[word] = []
            self.pathes[start] = [None]
            self.pathes[end] = []
    
            set1, set2, found = {start}, set(), False
            while not found:
                if len(set1) == 0:
                    return []
                for word in set1:
                    for ladder in self.nextLadder(word, dict, set2):
                        self.pathes[ladder].append(word)
                        if ladder not in set2:
                            set2.add(ladder)
                        if ladder == end:
                            found = True
                            break
    
                set1, set2 = set2, set()
    
            return self.getLadders(self.pathes, start, end)
    
        def nextLadder(self, word, dict, set2):
            for i in xrange(len(word)):
                for rep in self.alphabets:
                    cand = word[:i] + rep + word[i+1:]
                    if cand in dict and (len(self.pathes[cand]) == 0 or cand in set2):
                        yield cand
    
        def getLadders(self, pathes, start, end):
            ret = []
    
            if end == start:
                return [[start]]
    
            for ladder in pathes[end]:
                ret += self.getLadders(pathes, start, ladder)
            for path in ret:
                path.append(end)
    
            return ret
    

    use BFS and use a dictionary to store the parent string, and use sets to store current and next transformation.

    When I use list instead of set to store each transformation, it will be time limit extended.


Log in to reply
 

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