A transformation sequence from word beginWord
to word endWord
using a dictionary wordList
adheres to these rules:
beginWord
) must be in wordList
.endWord
.Given beginWord
, endWord
, and wordList
, find the length of the shortest transformation sequence from beginWord
to endWord
. Return 0
if no such sequence exists.
Example 1:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: "hit" -> "hot" -> "dot" -> "dog" -> "cog"
Example 2:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: endWord
is not in wordList
.
Constraints:
1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord != endWord
wordList
are unique.The most straightforward approach is to explore all possible transformation sequences from beginWord
until we reach endWord
. This can be done using a graph-like exploration, where each word in wordList
is a node, and edges connect words that differ by only one letter. A brute-force method would involve generating all possible paths and checking their validity.
beginWord
to endWord
.Big(O) Analysis:
wordList
. In the worst case, you might explore all possible permutations of words.This method is highly inefficient and impractical for larger dictionaries due to the exponential time complexity.
A more efficient approach involves using Breadth-First Search (BFS) to find the shortest transformation sequence. BFS guarantees that the first time we encounter endWord
, we've found the shortest path.
beginWord
and a distance of 1.wordList
:
endWord
, return the current distance + 1.endWord
is not found, return 0.Big(O) Analysis:
wordList
and M is the length of each word. The M2 comes from checking if two words differ by one letter (M to iterate through the letters, and another M in the worst case of string slicing). We do this for all N words in the worst case.wordList
.Edge Cases:
endWord
is not in wordList
, there is no transformation, so return 0.beginWord
is equal to endWord
, return 0 (as the problem states beginWord != endWord).wordList
is empty, and beginWord
is not endWord
, return 0 (no possible transformations).Code (Python):
from collections import deque
def ladderLength(beginWord: str, endWord: str, wordList: list[str]) -> int:
if endWord not in wordList:
return 0
wordList = set(wordList)
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, distance = queue.popleft()
if word == endWord:
return distance
for i in range(len(word)):
for char_code in range(ord('a'), ord('z') + 1):
char = chr(char_code)
new_word = word[:i] + char + word[i+1:]
if new_word in wordList and new_word not in visited:
queue.append((new_word, distance + 1))
visited.add(new_word)
return 0