You are given two words, beginWord and endWord, and a dictionary of words wordList. Your task is to find the shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.
Each transformed word must exist in the given wordList.

Return the length of the shortest transformation sequence. If there is no such transformation sequence, return 0.


beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.


Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the wordList.
You may assume beginWord and endWord are non-empty and are not the same.

from collections import deque

class Solution:
    def ladderLength(beginWord, endWord, wordList):
        if endWord not in wordList:
            return 0
        wordSet = set(wordList)
        queue = deque([(beginWord, 1)])
        visited = set()
        while queue:
            word, level = queue.popleft()
            if word == endWord:
                return level
            for i in range(len(word)):
                for char in 'abcdefghijklmnopqrstuvwxyz':
                    newWord = word[:i] + char + word[i+1:]
                    if newWord in wordSet and newWord not in visited:
                        queue.append((newWord, level + 1))
        return 0