Word Ladder

class Solution:
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        """
        替換字元變成新字串
        搜尋是否在wordlist 有則步驟 +1 然後加入 visited
        """        
        queue = collections.deque([(beginWord, 1)])
        alphabets = string.ascii_lowercase # abcd....z
        visited = set()
        while queue:
            word, length = queue.popleft()
            if word == endWord:
                return length          
            for i in range(len(word)):
                for char in alphabets:
                    strr = word[:i] + char + word[i+1:]
                    if strr in wordList and strr not in visited:
                        visited.add(strr)
                        queue.append((strr, length+1))
        return 0