from collections import deque

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        
        # Time O(n) Space O(n)
        
        # Suppose that we have a huge number of buckets, each of them with a four-letter word on the outside, except that one of the letters in the label has been replaced by an underscore.
        # See Figure 1 
        # We can implement the scheme we have just described by using a dictionary. 
        # The labels on the buckets we have just described are the keys in our dictionary. 
        # The value stored for that key is a list of words. 
        
        def construct_dict(word_list):
            d = {}
            for word in word_list:
                for char in range(len(word)):
                    # s is the label of buckets, i,e, key of the dictionary
                    s = word[:char] + "_" + word[char+1:]
                    # d[s] is the content of busckets, list of words. i.e. value of the dictinoary.
                    d[s] = d.get(s, []) + [word]
            # after the outer for loop, d is like:
            # e.x. d[_ope] = ["pope", "rope", "lope"]
            # d[p_pe] = ["pope", ‘pipe‘]
            # ... 
            
            return d
        
        
            
        # the input dict_words is in the format of the ouput if previous method
        # e.x. dict_words[_ope] = ["pope", "rope", "lope"]
        # dict_words[p_pe] = ["pope", ‘pipe‘]
        # ... 
        # the reason why the input dictinoary is in the "buscket" format is to save time... btw, tried the "non buscket " way, time exceeds limit...
        
        
        def bfs_words(begin, end, dict_words):
            queue, visited = deque([(begin, 1)]), set()
            # the queue stores the final path 
            while queue:
                # initiate word and steps; restore queue to empty when first come in
                # advance to examining the word just added to the queue in second and the following while loops
                word, steps = queue.popleft()
                if word not in visited:
                    visited.add(word)
                    if word == end:
                        return steps
                    for i in range(len(word)):
                        s = word[:i] + "_" + word[i+1:]
                        neigh_words = dict_words.get(s, [])
                        for neigh in neigh_words:
                            if neigh not in visited:
                                queue.append((neigh, steps + 1))
            return 0
        
        d = construct_dict(wordList)
        return bfs_words(beginWord, endWord, d)