A transformation sequence from word beginWord
to word endWord
using a dictionary wordList
is a sequence of words beginWord -> s1 -> s2 -> ... -> sk
such that:
si
for 1 <= i <= k
is in wordList
. Note that beginWord
does not need to be in wordList
.sk == endWord
Given two words, beginWord
and endWord
, and a dictionary wordList
, return the number of words in the shortest transformation sequence from beginWord
to endWord
, or 0
if no such sequence exists.
Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.
Example 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] Output: 0 Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
Constraints:
1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord
, endWord
, and wordList[i]
consist of lowercase English letters.beginWord != endWord
wordList
are unique.This problem asks for the length of the shortest transformation sequence from beginWord
to endWord
using words from wordList
, where each step involves changing only one letter.
This solution uses Breadth-First Search (BFS) to find the shortest transformation sequence. BFS guarantees that the first time we reach endWord
, we've found the shortest path.
Algorithm:
Initialization: Create a queue q
initialized with beginWord
, a set words
containing all words from wordList
, and a counter ans
initialized to 1 (representing the length of the sequence starting with beginWord
).
Iteration: While the queue is not empty:
ans
(each iteration represents one step deeper in the transformation).words
and is the endWord
, return ans
.words
and hasn't been visited, add it to the queue and remove it from words
(to avoid cycles).No Path: If the queue becomes empty without finding endWord
, it means there's no transformation sequence, so return 0.
Time Complexity: O(MNL), where M is the length of wordList, N is the length of each word, and L is the length of the alphabet (26). In the worst case, we might explore all possible variations of all words.
Space Complexity: O(M*N) in the worst case. The space is dominated by the queue and the words
set.
Code (Python):
from collections import deque
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
words = set(wordList)
q = deque([beginWord])
ans = 1
while q:
ans += 1
for _ in range(len(q)):
s = q.popleft()
s = list(s)
for i in range(len(s)):
ch = s[i]
for j in range(26):
s[i] = chr(ord('a') + j)
t = ''.join(s)
if t not in words:
continue
if t == endWord:
return ans
q.append(t)
words.remove(t) # Avoid cycles
s[i] = ch # Restore original character
return 0
Similar implementations exist in Java, C++, Go, and TypeScript, reflecting the same algorithm.
Bidirectional BFS optimizes the search by running two BFS searches simultaneously—one from beginWord
and one from endWord
. This reduces the search space, often significantly improving performance.
Algorithm:
Initialization: Two queues, q1
(from beginWord
) and q2
(from endWord
), are created, along with two maps, m1
and m2
, tracking distances from the starting points.
Iteration: The algorithm prioritizes expanding the smaller queue in each iteration. It checks for intersections between the queues. If a word is found in both queues, the shortest path has been found.
Termination: The search ends when either a path is found (intersection) or one of the queues becomes empty (no path).
Time Complexity: O(MN2^L), where M is the length of wordList, N is the length of words, and L is average word length. While still exponential in the worst case, it tends to be significantly faster than unidirectional BFS.
Space Complexity: O(M*N) in the worst case (due to the queues and maps)
Code (Python):
from collections import deque
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
words = set(wordList)
if endWord not in words: return 0 # Optimization: Early exit if endWord isn't in wordList
q1, q2 = deque([beginWord]), deque([endWord])
m1, m2 = {beginWord: 0}, {endWord: 0}
while q1 and q2:
if len(q1) <= len(q2):
res = self._extend(m1, m2, q1, words)
else:
res = self._extend(m2, m1, q2, words)
if res != -1:
return res + 1
return 0
def _extend(self, m1, m2, q, words):
for _ in range(len(q)):
s = q.popleft()
step = m1[s]
s_list = list(s)
for i in range(len(s_list)):
ch = s_list[i]
for j in range(26):
s_list[i] = chr(ord('a') + j)
t = "".join(s_list)
if t in m1 or t not in words: continue
if t in m2: return step + 1 + m2[t]
m1[t] = step + 1
q.append(t)
s_list[i] = ch
return -1
Again, comparable implementations can be written for other languages. The core bidirectional BFS strategy remains consistent. Note that while the worst-case complexity remains high, bidirectional BFS often offers a substantial performance advantage in practice.