Word Ladder

Given beginWord, endWord, and a wordList, return the length of the shortest transformation sequence from beginWord to endWord such that: each step changes exactly one letter, every intermediate word is in wordList, and the length counts all words in the sequence (including both ends). Return 0 if no such sequence exists. beginWord need not be in wordList, but endWord must be.

Hints

· Stuck? Reveal one nudge at a time.

Treat words as nodes; connect two words that differ by exactly one letter.

The shortest sequence is a shortest path — BFS from beginWord.

Find neighbours by trying all 26 letters at each position and checking a hash set.

Common doubts

The sequence lists every word visited, so the length is the number of nodes on the BFS path, including begin and end.

There are only 26·L possible one-letter neighbours of a word, independent of list size, so membership tests beat O(N) comparisons per word.

The sequence is just that word — length 1 (assuming it's a valid endpoint).

Interview follow-ups

· What an interviewer asks next.

Bidirectional BFS from both ends roughly halves the explored frontier.

That's Word Ladder II — track parents during BFS, then reconstruct the paths.

Fun facts

LeetCode 127 — Lewis Carroll invented word ladders in 1877.
Bidirectional BFS is the standard optimization interviewers look for here.

Asked at

AmazonFacebookGoogle

Frequently Sometimes Occasionally

Example 1

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

Example 2

Input: beginWord = "hit", endWord = "cog", wordList = [hot,dot,dog,lot,log]
Output: 0
endWord 'cog' isn't in the list, so no sequence exists.

Constraints

- 1 <= word length <= 10 - 1 <= wordList.length <= 5000 - all words have the same length - all words are lowercase and distinct

Hidden inside the word list is a graph: each word is a node, and two words are connected if they differ by exactly one letter. The shortest transformation sequence is then the shortest path from beginWord to endWord — and since every step costs 1, BFS finds it. The sequence length is the BFS depth at which endWord is reached.

The only real choice is how to find a word's neighbours:

Pairwise comparison — check every other word for a one-letter difference: O(N²·L) to explore.
Generate variations — for each position, try all 26 letters and test membership in a hash set: O(N·L·26), usually far faster.

Both do the same BFS and return the same length.

Prerequisites

Before you start

· Concepts used directly in the solution.

Words as a graph. edge = differ by one letter.

BFS shortest path. unit steps ⇒ BFS depth is the length.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Does the length include both ends?”

Yes — it counts every word in the sequence.

“Must endWord be in the list?”

Yes, or the answer is 0.

The ideal opening — say it like this

Words are nodes; one-letter changes are edges. I BFS from beginWord and return the depth at which I reach endWord.

I find neighbours by trying all 26 letters at each position and checking a hash set — much faster than comparing every pair.

Understand the problem

Worked example — begin = "hit", end = "cog", wordList = [hot, dot, dog, lot, log, cog]

hit -> hot -> dot -> dog -> cog  (or via lot/log)
length = 5

Key observations

1Aha

One-letter difference = edge

The word list is a graph.

2Aha

BFS depth = sequence length

Unit-step shortest path.

3Aha

Generate variations beats pairwise

26·L candidates vs comparing all N words.

Brute force vs optimal

	Pairwise BFS	Variation BFS
Neighbours	compare with every word	try 26 letters per position
Time	O(N²·L)	O(N·L·26)
Result	same length	same length

Both run the same BFS; generating variations is faster when the list is large. Full code is in the Approaches selector below.

Summary

Key takeaway

Words are nodes, one-letter changes are edges; BFS from beginWord gives the shortest length at endWord. Find neighbours by trying all 26 letters per position against a hash set.

BFS from begin; neighbour = one-letter change that's in the set
return depth at endWord, else 0