# mine
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:

        wordList.append(beginWord)
        from collections import defaultdict
        mapping = defaultdict(list)

        for word in wordList:
            for j in range(len(word)):
                pattern = word[:j] + "*" + word[j+1:]
                mapping[pattern].append(word)


        from collections import deque
        q = deque()
        visited = set()
        q.append(word)
        visited.add(word)
        res = 1

        while q:
            if endWord in q:
                return res

            for i in range(len(q)):
                word = q.popleft()

                for j in range(len(word)):
                    pattern = word[:j] + "*" + word[j+1:]
                    for neighbour in mapping[pattern]:
                        if neighbour not in visited:
                            q.append(neighbour)
                            visited.add(neighbour)
            res += 1

        return 0


# neetcode
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0

        nei = collections.defaultdict(list)
        wordList.append(beginWord)
        for word in wordList:
            for j in range(len(word)):
                pattern = word[:j] + "*" + word[j + 1 :]
                nei[pattern].append(word)

        visit = set([beginWord])
        q = deque([beginWord])
        res = 1
        while q:
            for i in range(len(q)):
                word = q.popleft()
                if word == endWord:
                    return res
                for j in range(len(word)):
                    pattern = word[:j] + "*" + word[j + 1 :]
                    for neiWord in nei[pattern]:
                        if neiWord not in visit:
                            visit.add(neiWord)
                            q.append(neiWord)
            res += 1
        return 0