PPractick

The problem

A word game asks players to turn one word into another by changing one letter at a time, where every intermediate word must be in the dictionary. What's the fewest words in such a sequence (counting both ends), or 0 if it's impossible? Treat words as vertices and one-letter changes as edges, and this is a shortest path in an unweighted graph, so BFS. Neighbours are generated on the fly by trying every letter at every position and keeping only dictionary words.

Example: hit → cog with dictionary [hot, dot, dog, lot, log, cog] → 5 (hit → hot → dot → dog → cog).

Function signature

int ladderLength(const string& beginWord, const string& endWord, const vector<string>& wordList);

Test cases

Input (begin, end, dictionary)	Output	Explanation
(hit, cog, [hot,dot,dog,lot,log,cog])	5	hit hot dot dog cog
(hit, cog, [hot,dot,dog,lot,log])	0	cog isn't in the dictionary
(a, c, [a,b,c])	2	a → c directly
(hot, dog, [hot,dog])	0	Two letters differ, and nothing is in between
(lost, cost, [most,fost,cost,host,lost])	2

(Confirm: all words have the same length and are lowercase; the begin word need not be in the dictionary, but the end word must be.)

How interviewers phrase it

• "Given beginWord, endWord and a dictionary, return the number of words in the shortest transformation sequence, or 0 if none exists" (LeetCode 127).

Clarifying questions to ask

1. Does the count include both endpoints? (Yes.)
2. Must endWord be in the dictionary? (Yes, otherwise return 0.)
3. How many words, and how long? (Up to 5000 words of length up to 10.)

Follow-ups to expect

1. "Why BFS?"
2. "How are neighbours generated efficiently?"
3. "How do you avoid revisiting?"
4. "Can it be faster?"
5. "Complexity?"

Related questions

• Alien Dictionary Hard
• Cycle Detection in Undirected Graph (bfs) Hard
• Word ladder II Hard
• Topological sort or Kahn's algorithm Hard
• Shortest path in undirected graph with unit weights Hard
• Shortest Distance in a Binary Maze Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in