WordLadder.py

# Question link - https://leetcode.com/problems/word-ladder/description/?envType=study-plan-v2&envId=top-interview-150

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        # Base case 
        if endWord not in wordList:
            return 0
        
        # create the adjacency list
        nei = collections.defaultdict(list)
        wordList.append(beginWord)

        # Createing the pattern 
        for word in wordList:
            for i in range(len(word)):
                pattern = word[:j] + "*" + word[j+1:]
                nei[pattern].append(word)

        # BFS 
        q = deque([beginWord])
        visited = set([beginWord])
        res = 1

        while q:
            for i in range(len(q)):
                word = q.popleft()
                if word == endWord:
                    return res
                
                # neighbors patterns
                for j in range(len(word)):
                    pattern = word[:j] + "*" + word[j+1:]

                    for neiWord in nei[pattern]:
                        if neiWord not in visited:
                            visited.add(neiWord)
                            q.append(neiWord)

            res += 1

        return 0