Участник:Turk0v/Word Ladder 2

Материал из DISCOPAL
Перейти к: навигация, поиск
class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        wordList = set(wordList)
        final_res = list()
        tmp_dict = dict()
        tmp_dict[beginWord] = [[beginWord]]
        while tmp_dict:
            newtmp_dict = defaultdict(list)
            for word in tmp_dict:
                if word == endWord:
                    return tmp_dict[word]
                else:
                    for i in range(len(word)):
                        for c in string.ascii_lowercase:
                            wordtmp = word[:i] + c + word[i+1:]
                            if wordtmp in wordList:
                                newtmp_dict[wordtmp] += [j + [wordtmp] for j in tmp_dict[word]]
            wordList -= set(newtmp_dict.keys())
            tmp_dict = newtmp_dict
        return final_res