127. Word Ladder

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        """tc  O(N* W*W)  sc O(N*W*W)  W: len(word) N: number of words in word list  
        1. preprocessing all string pattern with one character matches any char as hashmap   {h*t: [hit,hot]}
        2. start from biginWord do BFS, terminate untild find a pattern matches endWord
        3. mark used word to avoid repeated transformation  
        """
        queue = collections.deque([(beginWord, 1)])
        visited = set(beginWord)
        wordSet = set(wordList)
        while queue:
            word, level = queue.popleft()
            if word == endWord:
                return dist
            for i in range(len(word)):
                for j in string.ascii_lowercase:
                    new_word = word[:i] + j + word[i+1:]
                    if new_word not in visited and new_word in wordSet:
                        queue.append((new_word, level+1))
                        visited.add(new_word)
        return 0