Coding interview problems › Graphs & Grids

🗺️ Graphs & Grids Hard

Word Ladder

Word Ladder explained: words are nodes, one-letter changes are edges, and BFS finds the shortest chain. Tested Python with wildcard buckets and a live visual.

Also searched as: word ladder BFS · shortest transformation sequence between two words

🗺️

Try it live Free

Graph Search: BFS vs DFS

In the BFS vs DFS lab, watch BFS flood outward ring by ring and find the shortest path; in Word Ladder each ring is one more letter change.

Open the playground →

The problem

Given a start word, an end word and a dictionary, change one letter at a time so that every intermediate word is in the dictionary. Return the number of words in the shortest such chain from start to end (including both), or 0 if none exists.

Inputbegin = "hit", end = "cog", words = ["hot","dot","dog","lot","log","cog"]
Output5

hit -> hot -> dot -> dog -> cog

The key insight

Hidden inside is a graph: each word is a node, and two words are connected if they differ in exactly one letter. "Fewest changes" means shortest path in an unweighted graph, so BFS from the start word. To find neighbours fast, group words by wildcard patterns such as h*t: words sharing a pattern are one change apart.

Brute force first: Comparing every pair of words to build the graph costs O(n²·L) before BFS even starts, which is slow for large dictionaries.

Step-by-step approach

  1. If the end word is not in the dictionary, return 0.
  2. Build a map from each wildcard pattern (one letter replaced by *) to the words that match it.
  3. BFS from the start word with distance 1, marking words visited when they are pushed.
  4. For each popped word, look up all its patterns and push every unvisited word in those buckets with distance + 1.
  5. Return the distance when you pop the end word; if the queue empties, return 0.

Python solution

PYTHON 3tested
from collections import defaultdict, deque


def ladder_length(begin_word, end_word, word_list):
    words = set(word_list)
    if end_word not in words:
        return 0
    L = len(begin_word)
    buckets = defaultdict(list)        # "h*t" -> ["hot", "hit", ...]
    for w in words | {begin_word}:
        for i in range(L):
            buckets[w[:i] + "*" + w[i + 1:]].append(w)
    seen = {begin_word}
    q = deque([(begin_word, 1)])
    while q:
        word, d = q.popleft()
        if word == end_word:
            return d
        for i in range(L):
            key = word[:i] + "*" + word[i + 1:]
            for nxt in buckets[key]:
                if nxt not in seen:
                    seen.add(nxt)
                    q.append((nxt, d + 1))
            buckets[key] = []          # bucket fully used; never scan it again
    return 0

Complexity

TimeO(n·L²)
SpaceO(n·L²)

There are n words with L patterns each, and building every pattern string costs O(L), giving O(n·L²) to build buckets. Each bucket is scanned once during BFS because it is cleared after use.

Common mistakes

Frequently asked questions

What is the time and space complexity of Word Ladder?

With wildcard buckets it is O(n·L²) time and space, where n is the number of words and L the word length, because each word creates L patterns of length L.

Why BFS and not DFS?

All edges cost one change, so the problem is an unweighted shortest path. BFS visits words in order of distance, so the first time it reaches the end word it has used the fewest changes.

How can it be made faster?

Bidirectional BFS grows one frontier from each end and stops when they meet, always expanding the smaller frontier. That explores far fewer words on large dictionaries.

What does Word Ladder II ask?

It asks for all shortest chains, not just the length. Run BFS to record each word's distance or parents level by level, then backtrack from the end word to rebuild every shortest path.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Graphs & Grids Graph Search: BFS vs DFS lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.