Coding Interview PatternsWord Ladder
HardGraphs

Word Ladder

Explanation & Solution

Practice Problem

Description

Given two words beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, such that:

  • Only one letter can be changed at a time.
  • Each transformed word must exist in the wordList.

Return 0 if no such sequence exists.

Note that beginWord does not need to be in wordList.

Input:beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
0
hot
1
dot
2
dog
3
lot
4
log
5
cog

Output: 5

Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> "cog", which has 5 words.

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
  • All the words in wordList are unique

Approach

Graphs pattern

1. Early Exit Check

  • Convert wordList into a Set for O(1) lookups
  • If endWord is not in the set, return 0 immediately — no valid transformation exists

2. Initialize BFS

  • Create a queue starting with [beginWord, 1] where 1 represents the current sequence length
  • Create a visited set initialized with beginWord to avoid revisiting words

3. Process the Queue

  • Dequeue the front element to get the current word and its level (sequence length so far)
  • For each position i in the word, try replacing it with every letter from a to z
  • Skip if the replacement character is the same as the original

4. Check Each Neighbor

  • Build the newWord by replacing the character at position i
  • If newWord equals endWord, return level + 1 — we found the shortest path
  • If newWord exists in the word set and has not been visited, mark it as visited and add it to the queue

5. No Path Found

  • If the queue is exhausted without finding endWord, return 0

Key Insight

  • BFS guarantees the shortest path because it explores all words at distance k before any word at distance k+1
  • Using a Set for the word list gives O(1) lookup per candidate word, and trying all 26 letters at each position is efficient when word length is small
Time
O(M² × N) where M is word length and N is the size of the word list
Space
O(M × N) for the queue and visited set

Solution Code

Previous
Evaluate Division
Next
Cheapest Flights Within K Stops