Word Ladder
Last Updated: April 5, 2026
Understanding the Problem
We need to find the shortest path from beginWord to endWord, where each step changes exactly one letter, and every intermediate word must exist in the given wordList. The answer is the total number of words in that path (including both beginWord and endWord), not the number of steps.
This is fundamentally a shortest-path problem on an implicit graph. Each word is a node, and an edge exists between two words if they differ by exactly one letter. Since every edge has the same "cost" (one transformation), BFS is the natural choice for finding the shortest path.
The key challenge is efficiency. With up to 5000 words of length up to 10, naively comparing every pair of words to check if they differ by one letter would be expensive. The trick is to find a smarter way to discover neighbors.
Key Constraints:
1 <= wordList.length <= 5000-> We have at most 5000 words. An O(n^2) approach that compares every pair would be 25 million comparisons, each costing O(m) for string comparison. That's 250 million operations at word length 10, which is borderline.1 <= beginWord.length <= 10-> Words are short. This means we can enumerate all possible one-letter mutations of a word (26 * 10 = 260 possibilities) very quickly.beginWord != endWord-> No trivial case where start equals end.
Approach 1: BFS with Pairwise Comparison
Intuition
The most straightforward way to solve this is to treat it as a graph problem. Each word is a node, and two nodes are connected if they differ by exactly one character. We want the shortest path from beginWord to endWord, so BFS is the right tool since it explores nodes level by level and guarantees the shortest path in an unweighted graph.
For each word we dequeue during BFS, we scan the entire word list to find all words that differ by exactly one letter. Those are our neighbors.
Algorithm
- If
endWordis not inwordList, return 0 immediately since no transformation is possible. - Add all words from
wordListinto a set for O(1) lookup. - Initialize a BFS queue with
beginWordand a level counter starting at 1. - For each word dequeued, compare it against every remaining word in the set. If a word differs by exactly one character, add it to the queue and remove it from the set (to prevent revisiting).
- When we find
endWord, return the current level. - If the queue empties without finding
endWord, return 0.
Example Walkthrough
Input:
BFS explores level by level. Starting from "hit", we find "hot" (one letter different). From "hot", we find "dot" and "lot". From "dot", we find "dog". From "dog", we find "cog", our target. That gives us the path hit -> hot -> dot -> dog -> cog, which is 5 words.
Code
- Time Complexity: O(n^2 m). For each word we dequeue, we compare it against up to n remaining words in the set. Each comparison takes O(m) time where m is the word length. In the worst case, we process all n words, giving O(n^2 m).
- Space Complexity: O(n * m). The word set stores n words each of length m. The BFS queue holds at most n words.
This approach works but is slow for large inputs because we scan the entire word set for every dequeued word. What if we could generate all possible one-letter mutations and check if they exist in constant time?
Approach 2: BFS with Pattern Map
Intuition
Instead of comparing every pair of words, we can flip the problem around. For a word like "hot", we can generate wildcard patterns by replacing each character with a placeholder: "ot", "ht", "ho*". Any word matching the same pattern is exactly one letter away.
So we preprocess the word list: for each word, generate all its wildcard patterns, and store them in a map. The map key is the pattern, and the value is a list of words matching that pattern. Now during BFS, finding neighbors is just a matter of generating the current word's patterns and looking them up in the map.
This is much faster because generating patterns for a word of length m takes O(m) time, and each pattern lookup is O(1). Instead of comparing against n words, we check at most 26 * m possible mutations.
The pattern map is essentially a precomputed adjacency list. Two words are neighbors if and only if they share at least one wildcard pattern. By grouping words under their patterns, we avoid the O(n) scan per word during BFS. Instead, for each word, we generate m patterns (one per character position) and look up each pattern's word list in O(1). The total neighbors we examine per word is bounded by the actual number of neighbors, not the entire word list.
Algorithm
- If
endWordis not inwordList, return 0. - Build a pattern map: for each word in the word list (and
beginWord), replace each character position with '*' and map the pattern to all words matching it. - Initialize a BFS queue with
beginWord, a visited set containingbeginWord, and a level counter starting at 1. - For each word dequeued, generate its wildcard patterns. For each pattern, look up all matching words in the map.
- For each unvisited matching word, if it equals
endWord, return level + 1. Otherwise, mark it as visited and add it to the queue. - If the queue empties, return 0.
Example Walkthrough
Code
- Time Complexity: O(n m^2). Preprocessing builds the pattern map in O(n m^2). BFS visits each word once, generating m patterns with O(m) string operations per word.
- Space Complexity: O(n m^2). The pattern map stores n m entries, each key being a string of length m.
The pattern map BFS is efficient, but it still explores outward from one direction. What if we searched from both ends simultaneously and stopped when the two frontiers meet?
Approach 3: Bidirectional BFS
Intuition
Standard BFS explores outward from the start like a ripple in water. The search space grows exponentially at each level. Bidirectional BFS is a clever optimization: instead of searching only from beginWord, we also search from endWord and stop when the two frontiers meet.
Why is this faster? If the shortest path has length d and the branching factor is b, standard BFS explores roughly b^d nodes. Bidirectional BFS explores about 2 * b^(d/2) nodes, which is exponentially smaller. The trick is to always expand from the smaller frontier, keeping both frontiers roughly balanced.
Algorithm
- If
endWordis not inwordList, return 0. - Initialize two sets:
frontSetcontainingbeginWordandbackSetcontainingendWord. Also maintain avisitedset. - At each step, pick the smaller of the two sets to expand.
- For each word in the set being expanded, generate all possible one-letter mutations.
- If a mutation exists in the other set, the two frontiers have met. Return the current level.
- If a mutation exists in the word set and hasn't been visited, add it to a
nextSet. - Replace the expanded set with
nextSetand increment the level. - If either set becomes empty, return 0.
Example Walkthrough
Code
- Time Complexity: O(n * m). In the worst case, we visit all n words. For each word, we try 26 mutations at each of m positions. In practice, bidirectional BFS explores far fewer nodes because the two frontiers meet early.
- Space Complexity: O(n * m). The word set stores n words of length m. The visited set and frontier sets together hold at most n words.