Python solution in 578ms


  • 7
    C

    The trick is use set to save the words at each level because different words could ladder to the same word. It was 2580ms using list.

    alphabet = set('abcdefghijklmnopqrstuvwxyz')
    def findLadders(self, start, end, dict):
        dict.add(end)
        level_tracker = collections.defaultdict(set)
        self.parents_tracker = {}
        last = {start}
        while last and end not in level_tracker:
            current = set([])
            level_tracker.clear()
            for word in last:
                for next_word in self.ladder(word, dict):
                    if next_word not in self.parents_tracker:
                        current.add(next_word)
                        level_tracker[next_word].add(word)
            self.parents_tracker.update(level_tracker)
            last = current
        return [] if not last else self.generate_paths(start, end)
        
    def ladder(self, word, dict):
        for i in xrange(len(word)):
            for letter in self.alphabet - {word[i]}:
                new_word = word[:i] + letter + word[i + 1:]
                if new_word in dict:
                    yield new_word
    
    def generate_paths(self, start, end):
        ret = [[end]]
        while ret[-1][0] != start:
            new_ret = []
            for path in ret:
                for parent in self.parents_tracker[path[0]]:
                    new_ret.append([parent] + path)
            ret = new_ret
        return ret

  • 1
    N

    Thank you for making me look up what defaultdict do and generator too. :P


  • 0
    C

    no problem, those are awesome!


  • 1
    S

    Here is my version of generate_paths, which should be more efficient since it's appending items to a list instead of inserting items to the front of a list.

    def generate_paths(self, start, end):
        if start == end:
            return [[start]]
        paths = []
        for p in self.prev[end]:
            for path in self.generate_paths(start, p):
                paths.append(path + [end])
        return paths

  • 0
    W

    confuesd by list and set, we need to loop list or set both of them should be O(n)?
    why set makes it faster?


  • 0
    C

    Because list will allow duplicates which are ladder from different words, and the size of the list is much larger than that of the set


  • 0
    W

    amazing explain!!! thank you soooo much!


Log in to reply
 

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