Abstract / Summary

Find all shortest transformation sequences from a start word to an end word using words from a given list.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 28% (1+ million submissions).

Typical patterns to solve this problem:

• Backtracking
• Breadth First Search
• Hash Table
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The implementation solves the word-ladder transformation problem by first constructing a graph that connects words differing by a single character, then performing a forward breadth-first search to discover the minimal distance from the start word to every reachable word, and finally reconstructing all shortest transformation sequences by walking backward from the target word. The code is organized into three logical phases: preparation of the adjacency structure, forward exploration to capture the shortest depth levels, and backward assembly of the result paths.

Preparation of the adjacency structure

The algorithm begins by guaranteeing that the start word appears in the supplied list. If it is missing, the word is appended, ensuring that the subsequent graph construction includes it.

if beginWord not in wordList:
    wordList += [ beginWord ]

A helper generator dots yields every possible “dot pattern” of a word, where a single character is replaced by a period. For a word of length k the generator produces k patterns, each representing a potential one-character mutation.

def dots(w):
    for i in range(len(w)):
        yield w[:i] + "." + w[i+1:]

Using these patterns, the code builds a dictionary offbyone that maps each pattern to the list of words sharing it. This structure enables constant-time lookup of all words that are one edit away from any given word.

offbyone = defaultdict(list)
for w in wordList:
    for d in dots(w):
        offbyone[d].append(w)

Forward breadth-first search (pass 1)

The forward pass records the shortest distance (in number of steps) from the start word to every other word that can be reached. The dictionary shortest maps a depth level to the set of words discovered at that level. The set processed tracks words that have already been expanded, preventing redundant work.

shortest = defaultdict(set)
shortest[0] = set([ beginWord ])
processed   = set([ beginWord ])

The outer loop iterates up to the total number of words, each iteration representing an additional step in the ladder. For each word at the current depth, the algorithm enumerates its dot patterns, retrieves all neighboring words from offbyone, and adds any unprocessed neighbor to the next depth level. The list found collects newly discovered words for the current iteration.

for length in range(len(wordList)):
    found = []
    for word in shortest[length]:
        for i in dots(word):
            for next in offbyone[i]:
                if next not in processed:
                    shortest[length + 1].add(next)
                    found.append(next)

If the target word appears among the newly discovered words, the search terminates early because the minimal depth has been reached. If no new words are found, the function returns an empty list, indicating that no transformation sequence exists.

if endWord in found:
    break

if not found:
    return []
processed.update(found)

Backward reconstruction of all shortest ladders (pass 2)

Having recorded the minimal depth for each reachable word, the algorithm reconstructs every shortest path by walking backward from the end word. It starts with a list containing a single ladder consisting only of the target word.

result = [ [ endWord ] ]
step = max(shortest) - 1

While the current step index is non-negative, the code expands each partial ladder by prepending any word that is one edit away (as identified by the dot patterns) and that resides in the corresponding depth level of shortest. The newly formed ladders replace the previous collection, and the step counter is decremented.

while step >= 0:
    next = []
    for ladder in result:
        first = ladder[0]
        for i in dots(first):
            for prepend in offbyone[i]:
                if prepend in shortest[step]:
                    next.append([ prepend ] + ladder)

    result = next
    step  -= 1

When the loop finishes, result holds all transformation sequences that achieve the minimal number of steps, each represented as an ordered list from the start word to the end word.

return result

Edge cases addressed

The code explicitly handles the situation where the start word is absent from the input list by inserting it, ensuring that the graph remains connected to the source. When the forward search cannot progress because no new words are reachable, the function returns an empty list, correctly signaling the impossibility of a transformation. The early break condition when the end word is first encountered guarantees that only the shortest depth is recorded, preventing deeper, unnecessary exploration. The processed set eliminates revisiting words that have already been expanded, which also covers the case of duplicate entries in the word list.

Performance optimizations

Precomputing the dot pattern dictionary offbyone transforms the adjacency lookup from a linear scan over the entire word list to a constant-time retrieval based on pattern keys. The use of defaultdict(set) for shortest enables fast membership checks and avoids the overhead of list containment tests. The processed set ensures that each word is examined at most once during the forward pass, dramatically reducing the number of inner loop iterations. Early termination when the target word is found prevents the algorithm from traversing deeper levels that cannot contribute to a shorter path. In the backward reconstruction, limiting candidate predecessors to those present in the exact depth level stored in shortest prunes the search space to only those words that can belong to a shortest ladder, avoiding combinatorial explosion.

Imagine playing a game where you have to turn one word into another by changing only one letter at a time, like turning cat into bat and then into bet. This code is a clever helper that finds all the shortest paths to get from your starting word to your goal word.

First, the code organizes all the available words in a big pile. It looks at every word and hides one letter at a time, like turning cat into .at, c.t, and ca.. By doing this, it can quickly group words that are almost identical, which helps it see which words can jump to each other.

Next, the code starts a search. It begins with the starting word and looks for all the neighbors that are just one letter different. It keeps searching level by level, like climbing stairs, to find how many jumps it takes to reach the goal word. It keeps track of which words it has already visited so it never goes in circles.

Once the code knows the shortest distance needed to get to the final word, it does a second pass. This time, it works backward from the goal word to the start. It looks at the words that are one step closer and keeps building paths until it reaches the beginning. This creates a complete list of every possible path that takes the fewest number of steps. By the time it finishes, it has all the different ways to change the words while keeping the journey as short as possible.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python							TS
	WalkCCC	C++	Java	Python
	leetcode.ca		Java	Python						Go
	LeetcodeHelp	C++	Java	Python
	MemoryLimitExceeded	C++		Python
	Progiez	C++	Java	Python
github	aylei				Rust
	begeekmyfriend							C
	BigEggStudy						C#
	black-shadows	C++
	charles-wangkai		Java
	chenyanzhe	C++
	everthis					JS
	fartem								Ruby
	FelixFan1122		Java
	fpdjsns	C++
	gaosq0604			Python
	gouthampradhan		Java
	halfrost									Go
	JoshCrozier					JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007			Python
	luangong	C++
	qiyuangong			Python
	ruoru				Rust
	suxrobGM						C#
	vli02							C
	vthwang		Java
	wisdompeak	C++
	XiaotaoGuo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	Go, Java, Python
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fartem	Ruby
FelixFan1122	Java
fpdjsns	C++
gaosq0604	Python
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
luangong	C++
qiyuangong	Python
ruoru	Rust
suxrobGM	C#
vli02	C
vthwang	Java
wisdompeak	C++
XiaotaoGuo	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality