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 == endWordGiven 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 <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.lengthbeginWord, endWord, and wordList[i] consist of lowercase English letters.beginWord != endWordwordList are unique.Problem Overview: Given a beginWord, endWord, and a dictionary of valid words, compute the length of the shortest transformation sequence where only one character can change at a time and every intermediate word must exist in the dictionary.
Approach 1: Graph Construction + Breadth‑First Search (O(N^2 * L) time, O(N^2) space)
Treat every word as a node in a graph. Two nodes connect if the words differ by exactly one character. Building this graph requires comparing every pair of words and checking if they differ by one position, which costs O(N^2 * L) where N is the number of words and L is the word length. After constructing the adjacency list, run Breadth‑First Search from beginWord to find the shortest path to endWord. BFS guarantees the minimum number of transformations because it explores level by level. This approach is conceptually simple but wastes time building a dense graph that may never be fully explored.
Approach 2: BFS with Word Transformations (O(N * L * 26) time, O(N) space)
The optimized solution avoids explicitly building the entire graph. Store the dictionary in a hash table for O(1) lookups. Starting from beginWord, perform Breadth‑First Search. For each word popped from the queue, iterate through every character position and try replacing it with letters 'a' to 'z'. Each generated candidate word represents a possible transformation. If the word exists in the dictionary and hasn't been visited, push it into the queue and remove it from the set to prevent revisits. Each word can generate up to L * 26 neighbors, and each valid word is processed once, giving overall time complexity O(N * L * 26) with O(N) memory for the queue and visited structure. This method implicitly explores the graph without building it.
Recommended for interviews: The BFS transformation approach is the expected solution. It shows you recognize that the problem is a shortest‑path search in an unweighted graph and that you can generate neighbors dynamically using string manipulation. A brute-force graph build demonstrates understanding of the problem structure, but interviewers typically look for the optimized BFS that combines hashing and on‑the‑fly neighbor generation.
This approach leverages Breadth First Search (BFS), where each word is a node in the graph, and an edge exists between two nodes if they differ by exactly one letter. The goal is to find the shortest path from beginWord to endWord.
Start BFS from the beginWord, exploring transformations by changing each letter and checking if the new word exists in the set of available words. Polished implementation should consider preprocessing the word list for efficient lookup.
This C solution uses BFS to navigate from the beginWord to the endWord. It maintains a queue for exploration, marking words as visited to prevent revisiting them. The function oneLetterDifference checks if two words differ by exactly one letter, crucial for establishing edges in the BFS traversal.
Time Complexity: O(N * m^2), where N is the number of words in the list and m is the length of each word. Each word pair is compared in the worst case.
Space Complexity: O(N), where N is the number of nodes (words) we store in the queue.
BFS minimum step model. This problem can be solved with naive BFS, or it can be optimized with bidirectional BFS to reduce the search space and improve efficiency.
Bidirectional BFS is a common optimization method for BFS, with the main implementation ideas as follows:
while q1 and q2:
if len(q1) <= len(q2):
# Prioritize the queue with fewer elements for expansion
extend(m1, m2, q1)
else:
extend(m2, m1, q2)
def extend(m1, m2, q):
# New round of expansion
for _ in range(len(q)):
p = q.popleft()
step = m1[p]
for t in next(p):
if t in m1:
# Already visited before
continue
if t in m2:
# The other direction has been searched, indicating that a shortest path has been found
return step + 1 + m2[t]
q.append(t)
m1[t] = step + 1
| Approach | Complexity |
|---|---|
| Breadth First Search with Word Transformations | Time Complexity: O(N * m^2), where N is the number of words in the list and m is the length of each word. Each word pair is compared in the worst case. |
| BFS | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Explicit Graph Build + BFS | O(N^2 * L) | O(N^2) | Useful for understanding the graph structure or when the dataset is very small |
| BFS with On‑the‑Fly Word Transformations | O(N * L * 26) | O(N) | General case and interview‑optimal solution for large dictionaries |
G-29. Word Ladder - I | Shortest Paths • take U forward • 394,968 views views
Watch 9 more video solutions →Practice Word Ladder with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor