1
class Solution:
2
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
3
        e = defaultdict(list)
4
        m = len(beginWord)
5
        for word in wordList + [beginWord]:
6
            for i in range(m):
7
                w = word[:i] + "*" + word[i + 1 :]
8
                e[w].append(word)
9
        q = deque([beginWord])
10
        used = set([beginWord])
11
        d = 0
12
        while q:
13
            d += 1
14
            for _ in range(len(q)):
15
                word = q.popleft()
16
                for i in range(m):
17
                    w = word[:i] + "*" + word[i + 1 :]
18
                    if w in e:
19
                        for v in e[w]:
20
                            if v == endWord:
21
                                return d + 1
22
                            if v not in used:
23
                                q.append(v)
24
                                used.add(v)
25
                        e.pop(w)
26
        return 0