A transformation sequence from beginWord to endWord using dictionary wordList is a sequence where every adjacent pair of words differs by a single letter and every word is in wordList. Return the number of words in the shortest transformation sequence, or 0 if no such sequence exists.
1 <= beginWord.length <= 10, endWord.length == beginWord.length, wordList[i].length == beginWord.length, beginWord, endWord, and wordList[i] consist of lowercase English letters
BFS from beginWord. For each word, generate all possible one-letter variations and check if they exist in wordList. Track visited words.
from collections import deque
def ladderLength(beginWord, endWord, wordList):
word_set = set(wordList)
if endWord not in word_set:
return 0
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, length = queue.popleft()
if word == endWord:
return length
for i in range(len(word)):
for c in "abcdefghijklmnopqrstuvwxyz":
next_word = word[:i] + c + word[i+1:]
if next_word in word_set and next_word not in visited:
visited.add(next_word)
queue.append((next_word, length + 1))
return 0