from collections import defaultdict
from string import ascii_lowercase

class Solution(object):
    # Time: O(n * k * k) to build the graph. n = # of words. k = max number of character in a word
    # O(b ^ (d/2)) to perform a bidrectional BFS search, where b is the branching factor ( the average number of children(neighbors) at each node),
    # and d is the depth
    # Space: O(n * k)

    def word_ladder(self, start_word, end_word, word_list):
        """
        :type start_word: str
        :type end_word: str:
        :type word_list: Set[str]
        :rtye: int
        """

        if not start_word or not end_word or not word_list:
            return 0

        word_list.add(end_word)

        graph = self.build_graph(word_list)

        visited = set()
        length = 0
        front, back = {start_word}, {end_word}

        while front:
            if front & back:
                return length

            new_front = set()
            for word in front:
                visited.add(word)
                for i in range(len(word)):
                    wildcard = word[:i] + '-' + word[i + 1 :]
                    new_words = graph[wildcard]
                    new_words -= visited
                    new_front |= new_words
            
            front = new_front
            length += 1

            if len(back) < len(front):
                front, back = back, front
        
        return 0

    def build_graph(self, word_list):
        """
        :type word_list: Set[str]
        :rtype: defaultdict 
        """

        graph = defaultdict(set)
        for word in word_list:
            for i in range(len(word)):
                wildcard = word[:i] + '-' + word[i + 1 :]
                graph[wildcard].add(word)
        
        return graph