hardDSA

How do you solve the word ladder problem?

Q: How do you solve the word ladder problem?

**Intuition.** Think of each word as a **graph node**, with an edge between words that differ by exactly **one letter**. The shortest transformation sequence is then the shortest path in an unweighted graph — which is exactly what **BFS** finds. Generate neighbors on the fly by trying every position × every letter and checking the dictionary. BFS over one-letter edits: hit → … → cog (5 words) hit

816 views

Understand the problem

Explain shortest transformation via BFS.

graphsbfs

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

BFS over one-letter edits

Run Playground

from collections import deque

def ladder_length(begin, end, word_list):
    words = set(word_list)
    if end not in words:
        return 0
    q = deque([(begin, 1)])
    seen = {begin}
    while q:
        word, steps = q.popleft()
        if word == end:
            return steps
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                nxt = word[:i] + c + word[i + 1:]
                if nxt in words and nxt not in seen:
                    seen.add(nxt)
                    q.append((nxt, steps + 1))
    return 0


# --- demo ---
print(ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog']))   # 5

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How do you solve the trapping rain water problem?

What is the difference between Kruskal's and Prim's MST algorithms?