127. Word Ladder

Edited by Charles

Hard · Python · Graph

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

This problem can be viewed as a shortest path problem in an unweighted graph.

Original study notes follow, including intermediate snippets and earlier attempts.

Idea

This problem can be viewed as a shortest path problem in an unweighted graph.

We can think of:

Each word = a vertex

Two words are connected by an edge if they differ by exactly one character.

For example:

hit → hot → dot → dog → cog

Since every transformation has the same cost (1 step), we should use BFS to find the shortest transformation sequence.

BFS is suitable because it explores the graph level by level, so the first time we reach endWord, we have found the shortest path.

Graph Representation

We do not need to explicitly construct the entire graph.

Instead, for each current word, we generate all possible neighboring words by replacing each character with a-z.

For example:

word = "hit"

For the first position:

ait
bit
cit
...
zit

For the second position:

hat
hbt
hct
...
hzt

For the third position:

hia
hib
hic
...
hiz

If a generated word exists in wordList, then it is a valid neighbor.

Why Use a Set?

Convert wordList into a set:

wordSet = set(wordList)

We frequently need to check:

newWord in wordSet

Using a set gives approximately:

O(1)

lookup time.

Also, once a word is visited, we remove it from the set:

wordSet.remove(newWord)

This prevents the same word from being visited multiple times.

Therefore, wordSet also works as our visited structure.

BFS

Initialize the queue with:

queue = deque([(beginWord, 1)])

Each element contains:

(word, step)

where step represents the number of words in the current transformation sequence.

For example:

(hit, 1)

means the current sequence contains only:

hit

BFS Process

For each word removed from the queue:

word, step = queue.popleft()

If:

word == endWord

we return:

step

Otherwise, generate all possible words that differ by one character.

For every valid unvisited word:

if newWord in wordSet:

remove it from wordSet:

wordSet.remove(newWord)

and add it to the queue:

queue.append((newWord, step + 1))

Why BFS Instead of DFS?

Consider:

        B
       /
A ----
       \
        C → D → E

There may be many different transformation paths.

DFS may explore a very long path before finding the destination.

BFS explores by distance:

Level 1: distance 1
Level 2: distance 2
Level 3: distance 3
...

Therefore, the first time BFS reaches endWord, that path must be the shortest transformation sequence.

A useful rule is:

Reachability problem
→ DFS or BFS

Shortest path in an unweighted graph
→ BFS

Hand Simulation

Consider:

beginWord = "hit"
endWord = "cog"

wordList = [
    "hot",
    "dot",
    "dog",
    "lot",
    "log",
    "cog"
]

Initially:

queue = [(hit, 1)]

Level 1

Pop:

(hit, 1)

Generate its valid neighbor:

hit → hot

Queue becomes:

[(hot, 2)]

Level 2

Pop:

(hot, 2)

Valid unvisited neighbors:

hot → dot
hot → lot

Queue:

[(dot, 3), (lot, 3)]

Level 3

From dot:

dot → dog

From lot:

lot → log

Queue:

[(dog, 4), (log, 4)]

Level 4

From dog:

dog → cog

So:

queue = [(log, 4), (cog, 5)]

Eventually we pop:

(cog, 5)

Since:

word == endWord

return:

5

The shortest transformation sequence is:

hit → hot → dot → dog → cog

which contains 5 words.

Important Detail: Why Is the Answer 5 Instead of 4?

There are four transformations:

hit → hot
hot → dot
dot → dog
dog → cog

However, the problem asks for the number of words in the transformation sequence, not the number of edges.

Therefore:

hit → hot → dot → dog → cog
 1      2      3      4      5

The answer is:

5

This is why we initialize:

queue = deque([(beginWord, 1)])

instead of starting with 0.

Important Detail: endWord Must Exist

If:

endWord not in wordSet

there is no valid transformation sequence because every transformed word must exist in wordList.

Therefore:

if endWord not in wordSet:
    return 0

Complexity Analysis

Let:

N = number of words
L = length of each word

For each word, we try:

L positions × 26 characters

Therefore, ignoring the cost of Python string construction, the main search work is approximately:

O(N × L × 26)

With string construction included, it can be viewed as:

O(N × L²)

since creating each candidate string costs O(L).

Space Complexity:

O(N)

for the set and BFS queue, aside from storage for generated strings.

Summary

1. Treat every word as a vertex.
2. Two words have an edge if they differ by one character.
3. The problem becomes an unweighted shortest-path problem.
4. Use BFS.
5. Generate neighbors by replacing each character with a-z.
6. Use a set for fast lookup.
7. Remove words from the set once visited.
8. Store (word, step) in the queue.
9. Return step when endWord is reached.

The most important idea is:

Word Ladder is a hidden unweighted graph shortest-path problem, so BFS is the natural solution.

Study record

Field	Value
Attempts	1
Mastery	❚
The Latest Attempt	August 20, 2026

Python solution

from collections import deque

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordSet = set(wordList)

        if endWord not in wordSet:
            return 0

        queue = deque([(beginWord, 1)])

        while queue:
            word, step = queue.popleft()
            if word == endWord:
                return step

            for i in range(len(word)):
                for char in string.ascii_lowercase:
                    newWord = word[: i] + char + word[i + 1:]
                    if newWord in wordSet:
                        wordSet.remove(newWord)
                        queue.append((newWord, step + 1))

        return 0

---

Back to Day 46 Graph IV · All Algorithm notes