Editor

Word Ladder

#179 · Graphs · Expert · 210 XP · about 35 min

A word ladder turns one word into another in steps. Each step changes exactly one letter, and every word you step onto must be in the list words. For example, 'cold' can become 'cord', then 'card', then 'ward' and finally 'warm'.

Write ladder_length(start, goal, words) that returns the number of words in the shortest ladder from start to goal, counting both ends, or 0 if no ladder exists. start does not have to be in words, but goal does.

Examples

words = ['cord', 'card', 'ward', 'warm', 'word', 'worm', 'core']
ladder_length('cold', 'warm', words)  # returns 5
ladder_length('lead', 'gold', ['load', 'goad', 'gold', 'lend'])  # returns 4
ladder_length('cat', 'dog', ['cot', 'cog'])  # returns 0

The first ladder is cold, cord, card, ward, warm: five words. In the last example 'dog' is not in the list, so it can never be reached.

Constraints

  • All words have the same length, from 1 to 10 lowercase letters.
  • words holds up to 5,000 words, and start and goal are different.

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.