word_ladder.py

# noinspection PyPep8Naming
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        d = defaultdict(list)
        for word in wordList:
            for i in range(len(word)):
                d[word[:i], word[i + 1:]].append(word)
        seen = {beginWord}
        q = [beginWord]
        steps = 1
        while q:
            new_q = []
            for word in q:
                if word == endWord:
                    return steps
                for i in range(len(word)):
                    for w in d[word[:i], word[i + 1:]]:
                        if w not in seen:
                            seen.add(w)
                            new_q.append(w)
            steps += 1
            q = new_q
        return 0