Python simple BFS layer by layer


  • 2
    A
    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])
                    else:
                        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.