126. Word Ladder II (Hard) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def findLadders(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: List[List[str]]
        """
        result = [beginWord](/TengnanYao/daily_leetcode/wiki/beginWord)
        w = set(wordList)
        found = False
        while True:
            temp = []
            used = set()
            count = 0
            for li in result:
                cur = li[-1]
                for i in range(len(cur)):
                    for c in "qwertyuiopasdfghjklzxcvbnm":
                        word = cur[ : i] + c + cur[i + 1 : ]
                        if word in w:
                            count += 1
                            temp.append(li + [word])
                            used.add(word)
                            if word == endWord:
                                found = True
            if not count:
                return []
            w -= used
            result = temp
            if found:
                return [x for x in result if x[-1] == endWord]