Fixed code for https://stackoverflow.com/questions/53075364

x.py

import collections


class Solution:
    def findLadders(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: List[List[str]]
        """
        wordListSet = set(wordList + [beginWord])
        graph = collections.defaultdict(list)
        q = set([beginWord])
        count = 0
        result = []
        while q:
            count += 1
            newQ = set()
            for word in q:
                wordListSet.remove(word)
            for word in q:
                if word == endWord:
                    self.getAllPaths(graph, beginWord, endWord, result, [])
                else:
                    for i in range(len(word)):
                        for sub in 'abcdefghijklmnopqrstuvwxyz':
                            if sub != word[i]:
                                newWord = word[:i] + sub + word[i + 1:]
                                if newWord in wordListSet:
                                    graph[word].append(newWord)
                                    newQ.add(newWord)
            q = newQ
        return result

    def getAllPaths(self, graph, node, target, result, output):
        # This is just a backtracking pre-order traversal DFS on a DAG.
        output.append(node)
        if node == target:
            result.append(output[:])
        else:
            for child in graph[node]:
                self.getAllPaths(graph, child, target, result, output)
                output.pop()


beginWord = 'aaa'
endWord = 'cdd'
wordList = ['aab', 'aba', 'abb', 'cbb', 'cbd', 'cdb', 'cdd']

s = Solution()
out = s.findLadders(beginWord, endWord, wordList)
print(out)
# [['aaa', 'aba', 'abb', 'cbb', 'cdb', 'cdd'], ['aaa', 'aba', 'abb', 'cbb', 'cbd', 'cdd'],
#  ['aaa', 'aab', 'abb', 'cbb', 'cdb', 'cdd'], ['aaa', 'aab', 'abb', 'cbb', 'cbd', 'cdd']]