Clean Two-way BFS in Python


  • 0
    tree = lambda: collections.defaultdict(tree)
    
    
    def genPaths(tree, word):
        if not tree[word]:
            return [[word]]
    
        return [
            [word] + path
            for child in tree[word]
            for path in genPaths(tree[word], child)
        ]
    
    
    class Solution(object):
        def findLadders(self, beginWord, endWord, wordList):
            forward, backward, pairs = {beginWord: tree()}, {endWord: tree()}, []
    
            while forward and backward:
                if len(backward) < len(forward):
                    forward, backward = backward, forward
    
                nextRow, trash = tree(), set()
                for word in forward:
                    for i in xrange(len(word)):
                        for char in string.ascii_lowercase:
                            candidate = word[:i] + char + word[i + 1:]
                            if candidate in backward:
                                pairs.append([word, candidate])
                                continue
    
                            if candidate in wordList:
                                nextRow[candidate][word] = forward[word]
                                trash.add(candidate)
                if pairs:
                    break
    
                wordList -= trash
                forward = nextRow
    
            cache, r = {}, []
            for word1, word2 in pairs:
                pathForward = cache.setdefault(word1, genPaths(forward, word1))
                pathBackward = cache.setdefault(word2, genPaths(backward, word2))
    
                if pathBackward[0][-1] == beginWord:
                    pathForward, pathBackward = pathBackward, pathForward
    
                r += [p1[::-1] + p2 for p1 in pathForward for p2 in pathBackward]
    
            return r
    

Log in to reply
 

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