Word Ladder
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Change one letter at a time, each step must be a word from a list, to turn beginWord into endWord. Return the number of words in the shortest sequence (0 if impossible).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1How many neighbours can a word of length L have? Try changing each position to each letter.
- Hint 2Remove a word from the unseen set when you first reach it so it is not visited again.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
The word-ladder game: hit -> hot -> dot -> dog -> cog. You wander outward like a ripple in a pond: first every word one change away, then every word two changes away, and so on. The first ripple that touches the target tells you the shortest ladder. Words used once never need to be visited again.
- The obvious way
DFS exploring all ladders and keeping the shortest: exponential.
- The key insight
Keep the current ripple (a set of words) and the set of unseen words. Each round: if the ripple contains the end word, return the round number. Otherwise build the next ripple by trying, for each word, every letter in every position; any result still in the unseen set joins the next ripple and leaves the unseen set. If the ripple dies out, return 0.
- The algorithm
- ripple = {begin word}; unseen = all words; length = 1.
- End word in the ripple? Return length.
- Next ripple = unseen words one letter away from any word in this ripple (remove them from unseen).
- length + 1 and repeat; empty ripple: 0.
Watch it run
Examplebegin = hit, end = cog, words = [hot, dot, dog, lot, log, cog]
Ripple 1 is {hit}. Changing one letter reaches hot only.
length 1
Where people slip
- The answer counts words (including both ends), not changes.
- If the end word is not in the list, return 0 straight away.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def ladder_length(begin_word, end_word, word_list):
unseen = set(word_list)
if end_word not in unseen:
return 0
unseen.discard(begin_word)
ripple = {begin_word}
length = 1
letters = "abcdefghijklmnopqrstuvwxyz"
while ripple:
if end_word in ripple:
return length
next_ripple = set()
for word in ripple:
for position in range(len(word)):
for letter in letters:
candidate = word[:position] + letter + word[position + 1:]
if candidate in unseen:
unseen.remove(candidate) # never visit a word twice
next_ripple.add(candidate)
ripple = next_ripple
length += 1
return 0Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.