Word Ladder

Hard#127states

You get a begin word, an end word and a list of words of the same length. A ladder goes from the begin word to the end word, changing one letter at a time, and every word after the first must be in the list. Return how many words the shortest ladder has, counting both ends, or 0 if there is none. Our example: sit → pan with the list [pit, sat, pat, pan] — the answer is 4.

127 Word LadderWalkthrough · 1×

Example: the shortest ladder from sit to pan through the list [pit, sat, pat, pan], counted in words.

1 word2 words3 words4 wordssitwordSetpitsatpatpanqueuefront on the left—
in the set, not reachedwaiting in the queuecurrent wordone letter awaydonetaken out of the set

Put the list in a set: {pit, sat, pat, pan}

01/37
restart · back · play · step
Speed
1function ladderLength(begin, end, words):
2 wordSet = set(words)
3 if end not in wordSet:
4 return 0
5 queue = [begin]
6 steps = 1
7 while queue is not empty:
8 repeat queue.size times:
9 word = queue.popFront()
10 for next in oneLetterAway(word):
11 if next == end:
12 return steps + 1
13 if next in wordSet:
14 wordSet.remove(next)
15 queue.pushBack(next)
16 steps = steps + 1
17 return 0
state
wordSet
{pit, sat, pat, pan}
queue
–
steps
–
word
–
next
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. BFS goes level by level and steps counts the words up to the current level, so the first time the end word comes up, steps + 1 is the shortest ladder.
  2. A word is taken out of the set the moment it is queued: a second word of the same level that leads to it finds it gone, so nothing is queued twice and no visited set is needed.
  3. If the end word is not in the list, no ladder can end there, so the answer is 0 before any search.

Complexity

Time O(n · 26 · L²) for n words of length L: each word is queued once and tries 26 letters in each of its L places, and making and looking up each new word takes O(L). Memory O(n) for the set and the queue.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.