Word Ladder

Table of Contents +

Word Ladder looks like a word puzzle. But it is really a graph question in disguise. The interviewer wants to see if you can spot the hidden graph and then find the shortest path through it. That is the whole game here.

🎯 The Problem

You get a start word, an end word, and a list of allowed words, and must find the shortest transformation chain.

You turn the start word into the end word.
You may change one letter at a time.
After every single change, the new word must still be in the word list.
Return how many words are in the shortest chain, counting both ends.
If no valid chain exists, return 0.

Let us say the start word is hit and the end word is cog. The word list is ["hot", "dot", "dog", "lot", "log", "cog"]. One shortest chain is hit -> hot -> dot -> dog -> cog. That chain has five words. So the answer is 5.

Input:  beginWord = "hit", endWord = "cog"
        wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
Output: 5

Explanation: hit -> hot -> dot -> dog -> cog has 5 words.

Here is the hidden graph. Each word is a node, which means a point in the graph. Two words are joined by an edge when they differ by exactly one letter. An edge is just a line that connects two nodes.

🐢 Approach 1: Depth-First Search (Brute Force)

Follow one chain all the way down before trying another.

The idea:

A depth-first search follows one path to its end before backing up.
Start at the begin word. Try every word that differs by one letter.
From each of those, go deeper, and keep going until you reach the end word.

Why it is weak:

It explores long paths before short ones.
So you waste huge effort on chains far longer than needed.
You also risk going in circles unless you track visited words.
For a real word list this becomes far too slow.

Here is the DFS search code:

def ladder_length(begin_word, end_word, word_list):
    words, best = set(word_list), float("inf")
    def one_diff(a, b): return sum(x != y for x, y in zip(a, b)) == 1
    def dfs(word, seen, length):
        nonlocal best
        if word == end_word:
            best = min(best, length); return
        for nxt in list(words):
            if nxt not in seen and one_diff(word, nxt):
                dfs(nxt, seen | {nxt}, length + 1)
    dfs(begin_word, {begin_word}, 1)
    return 0 if best == float("inf") else best

⚡ Approach 2: Breadth-First Search (Best)

The idea in one line: explore the graph level by level, so the first time you touch the end word is the shortest chain.

The idea:

Breadth-first search, called BFS, explores in layers.
All words one step away first. Then two steps. Then three. And so on.
The first time BFS reaches the end word, it must be by the shortest chain.

How it works:

Use a queue, a line where the first item in is the first item out.
Push the begin word with distance one. Pop words off the front.
For each word, build its one-letter neighbors. Push each unvisited neighbor with distance plus one.
When you pop the end word, its distance is the answer.

Building neighbors fast:

Do not compare every pair of words.
For the current word, change each letter position to every letter a to z.
If the new word is in the list and not yet visited, it is a neighbor.
Mark words visited by removing them from the set, so you never process one twice.

Here is the BFS code:

from collections import deque
def ladder_length(begin_word, end_word, word_list):
    words, q = set(word_list), deque([(begin_word, 1)])
    while q:
        word, dist = q.popleft()
        if word == end_word: return dist
        for i in range(len(word)):
            for ch in "abcdefghijklmnopqrstuvwxyz":
                nxt = word[:i] + ch + word[i+1:]
                if nxt in words:
                    words.remove(nxt); q.append((nxt, dist + 1))
    return 0

🧭 Approach 3: Two-Ended BFS (Alternative)

The idea in one line: search from both the begin word and the end word at the same time and meet in the middle.

The idea:

Run BFS from both ends at once.
Always expand the smaller frontier next.
Stop when the two searches touch a shared word.

Why it can be faster:

The graph branches out, so a single BFS grows fast.
Two half-depth searches touch far fewer words than one full-depth search.
It gives the same shortest length, just with less work on big word lists.

Why it is trickier:

You manage two frontiers and must swap to the smaller one each round.
The meeting check needs care. Reach for plain BFS first, then mention this.

Here is the BFS spreading out in layers from hit. Each layer is one more step away.

Steps to Solve

Put all words from the word list into a set for instant lookup.
If the end word is not in that set, return 0 right away.
Create a queue and push the begin word with distance 1.
Pop a word from the queue. If it equals the end word, return its distance.
For each letter position, try every letter a to z to build a new word.
If the new word is in the set and not visited, mark it visited and push it with distance plus one.
Repeat until the queue is empty. If you never reach the end word, return 0.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version uses a set for the word list and a deque as the queue, which pops from the front fast.

from collections import deque


def ladder_length(begin, end, word_list):
    words = set(word_list)        # fast lookup for valid words
    if end not in words:          # no chain is possible
        return 0

    queue = deque([(begin, 1)])   # each item is (word, distance)

    while queue:
        word, dist = queue.popleft()
        if word == end:           # reached the end word
            return dist

        for i in range(len(word)):
            for c in "abcdefghijklmnopqrstuvwxyz":
                nxt = word[:i] + c + word[i + 1:]   # change one letter
                if nxt in words:
                    words.remove(nxt)               # mark visited
                    queue.append((nxt, dist + 1))
    return 0                      # no chain found


word_list = ["hot", "dot", "dog", "lot", "log", "cog"]
print(ladder_length("hit", "cog", word_list))

The output of the above code will be:

Let us walk through the Python version line by line. We do code first, then the why.

We start with words = set(word_list). We put the list into a set so we can ask “is this a word?” in almost no time. A list would force us to scan every item.

Then if end not in words: return 0. If the end word is not even allowed, no chain can ever reach it. So we stop early.

Next queue = deque([(begin, 1)]). We seed the queue with the begin word at distance one. The distance counts how many words are in the chain so far. The begin word alone is a chain of length one.

The loop while queue: runs until we run out of words to explore. Inside, word, dist = queue.popleft() takes the oldest word first. That front-first order is what makes this BFS, so we always finish the closer words before the farther ones.

if word == end: return dist is the win. The first time we pop the end word, its distance is the shortest chain length. BFS guarantees that.

The two inner loops build neighbors. for i in range(len(word)) picks a position. for c in "abc...z" tries each letter there. nxt = word[:i] + c + word[i+1:] rebuilds the word with one letter swapped.

if nxt in words: checks the new word is real and not yet used. We then words.remove(nxt) to mark it visited. Removing it from the set is a neat trick. It both records the visit and blocks any repeat. Finally queue.append((nxt, dist + 1)) pushes the neighbor one step farther out.

⏱️ Time and Space Complexity

Let n be the number of words and L be the length of each word. For each word we try L positions times 26 letters. So building neighbors costs about 26 * L work per word. The set lookups are almost instant. So the whole BFS runs in O(n * L * 26) time, which we usually write as O(n * L). The space holds the queue and the set, so it is O(n * L) too.

Approach	Time Complexity	Space Complexity
Depth-first search (brute force)	Exponential	O(n * L)
Breadth-first search	O(n * L * 26)	O(n * L)
Two-ended BFS	O(n * L * 26)	O(n * L)

Tip

The key sentence to say in the interview is short. “Shortest path on an unweighted graph means BFS.” If you can name that, the rest is just careful coding.

🧩 Key Takeaways

✅ Word Ladder is a shortest-path question hiding inside a word puzzle.
✅ Each word is a node. Two words are joined when they differ by one letter.
✅ BFS explores level by level, so the first time it reaches the end word is the shortest chain.
✅ Build neighbors by swapping each letter to a through z, then checking the set.
✅ Remove a word from the set once visited, so you never process it twice.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Word Ladder II
Shortest Path in Binary Matrix

Previous Graph Valid Tree Next Word Ladder II

Word Ladder

Follow Us

Follow Us