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])
                            if candidate in wordList:
                                nextRow[candidate][word] = forward[word]
                if pairs:
                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.