Python simple BFS layer by layer

  • 2
    class Solution(object):
        def findLadders(self, beginWord, endWord, wordList):
            wordList = set(wordList)
            res = []
            layer = {}
            layer[beginWord] = [[beginWord]]
            while layer:
                newlayer = collections.defaultdict(list)
                for w in layer:
                    if w == endWord: 
                        res.extend(k for k in layer[w])
                        for i in range(len(w)):
                            for c in 'abcdefghijklmnopqrstuvwxyz':
                                neww = w[:i]+c+w[i+1:]
                                if neww in wordList:
                                    newlayer[neww]+=[j+[neww] for j in layer[w]]
                wordList -= set(newlayer.keys())
                layer = newlayer
            return res

Log in to reply

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