AlgoMaster Logo

Word Ladder

hardFrequency9 min readUpdated June 23, 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 challenge is efficiency. With up to 5000 words of length up to 10, comparing every pair of words to check if they differ by one letter is expensive. The approaches below differ mainly in how they discover a word's neighbors.

Key Constraints:

  • 1 <= wordList.length <= 5000 -> At most 5000 words. Comparing every pair is up to 25 million comparisons, each costing O(m) for the string check, around 250 million operations at word length 10. That is slow enough to motivate a faster way to find neighbors.
  • 1 <= beginWord.length <= 10 -> Words are short, so enumerating all one-letter mutations of a word (26 * 10 = 260 possibilities) is cheap.
  • beginWord != endWord -> The start and end are always distinct.

Approach 1: BFS with Pairwise Comparison

Intuition

Treat this as a graph problem. Each word is a node, and two nodes are connected if they differ by exactly one character. Since every edge costs the same single transformation, BFS finds the shortest path: it explores nodes level by level, so the first time it reaches a word, it has reached it by the fewest transformations.

The simplest way to find neighbors is direct comparison. For each word dequeued during BFS, scan the entire word list and keep every word that differs from it by exactly one letter.

Algorithm

  1. If endWord is not in wordList, return 0 immediately since no transformation is possible.
  2. Add all words from wordList into a set for O(1) lookup.
  3. Initialize a BFS queue with beginWord and a level counter starting at 1.
  4. 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).
  5. When we find endWord, return the current level.
  6. If the queue empties without finding endWord, return 0.

Example Walkthrough

Input:

0
h
1
i
2
t
beginWord
0
c
1
o
2
g
endWord
0
hot
1
dot
2
dog
3
lot
4
log
5
cog
wordList

BFS explores level by level, and level counts the words on the path so far.

  • Level 1: Queue holds ["hit"]. Dequeue "hit", scan the set, and "hot" differs by one letter. It is not endWord, so add it to the queue and remove it from the set. Queue is now ["hot"], then increment level to 2.
  • Level 2: Dequeue "hot". Scanning the set finds "dot" and "lot", both one letter away. Neither is "cog", so add both. Queue is ["dot", "lot"], level becomes 3.
  • Level 3: Dequeue "dot", which connects to "dog". Dequeue "lot", which connects to "log". Queue is ["dog", "log"], level becomes 4.
  • Level 4: Dequeue "dog". Scanning the set, "cog" differs by one letter and equals endWord, so return level + 1 = 5.

The path is hit -> hot -> dot -> dog -> cog, five words.

5
output

Code

This is slow for large inputs because every dequeued word triggers a full scan of the word set. The next approach finds neighbors without scanning, by precomputing which words are one letter apart.

Approach 2: BFS with Pattern Map

Intuition

For a word like "hot", replace each character position with a placeholder to get its wildcard patterns: "ot", "ht", "ho*". Two words differ by exactly one letter if and only if they share one of these patterns, because the shared pattern fixes every position except the one wildcard.

Preprocess the word list once: for each word, generate all its wildcard patterns and store them in a map from pattern to the list of words matching it. During BFS, finding a word's neighbors becomes generating its m patterns and looking each up in the map. Generating patterns for a word of length m takes O(m) time and each lookup is O(1), so neighbor discovery touches the actual neighbors rather than scanning all n words.

Algorithm

  1. If endWord is not in wordList, return 0.
  2. 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.
  3. Initialize a BFS queue with beginWord, a visited set containing beginWord, and a level counter starting at 1.
  4. For each word dequeued, generate its wildcard patterns. For each pattern, look up all matching words in the map.
  5. For each unvisited matching word, if it equals endWord, return level + 1. Otherwise, mark it as visited and add it to the queue.
  6. If the queue empties, return 0.

Example Walkthrough

With the pattern map built, BFS walks the implicit graph below. Each color shows the BFS state: green for fully processed words, yellow for the current frontier. Patterns like "ht" and "ot" are what link each word to its neighbors.

1Level 1: Start BFS from "hit", queue = ["hit"]
hitstarthotdotlotdoglogcog
1/6

Code

The pattern map BFS is efficient, but it still expands outward from a single source, and the frontier grows wider at every level. The next approach searches from both ends at once and stops when the two frontiers meet, which cuts the number of explored words.

Approach 3: Bidirectional BFS

Intuition

Standard BFS expands outward from the start, and the frontier roughly multiplies by the branching factor at each level. Bidirectional BFS searches from beginWord and endWord at the same time and stops when the two frontiers share a word.

This is faster because of the exponents. If the shortest path has length d and the branching factor is b, standard BFS explores roughly b^d words. Each half of a bidirectional search only needs to reach the midpoint, so the two searches explore about 2 * b^(d/2) words combined, which is far smaller for large d. To keep the two halves balanced, each step expands whichever frontier is currently smaller, since that one generates fewer mutations to process.

Algorithm

  1. If endWord is not in wordList, return 0.
  2. Initialize two sets: frontSet containing beginWord and backSet containing endWord. Also maintain a visited set.
  3. At each step, pick the smaller of the two sets to expand.
  4. For each word in the set being expanded, generate all possible one-letter mutations.
  5. If a mutation exists in the other set, the two frontiers have met. Return the current level.
  6. If a mutation exists in the word set and hasn't been visited, add it to a nextSet.
  7. Replace the expanded set with nextSet and increment the level.
  8. If either set becomes empty, return 0.

Example Walkthrough

The front frontier (yellow) grows from "hit" and the back frontier (blue) grows from "cog". The search ends when a word generated from one side already sits in the other side's set. Here the frontiers meet at "dog", giving a path of 5 words.

1Initialize: frontSet={"hit"}, backSet={"cog"}, level=1
hitfronthotdotlotdoglogcogback
1/6

Code