progress

~/problems / Graphs / BFS / multi-source BFS

Word Ladder

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

hard ~40 min

In a word puzzle you turn one word into another by changing a single letter at a time, and every word you pass through (including the final one) must be in the puzzle's words list. The starting word doesn't need to be in the list.

Write shortest_chain(start, goal, words) -> int that returns the number of words in the shortest chain from start to goal, counting both ends, or 0 if goal can't be reached.

  • All words (start, goal and everything in words) have the same length and use lowercase letters a-z.
  • A step changes the letter at exactly one position; letters never move, and nothing is added or removed.
  • start != goal. words may contain duplicates and may contain start.
shortest_chain("same", "cope", ["came", "cane", "cone", "cope", "sane", "sine", "core"])
# 5   (same -> came -> cane -> cone -> cope)
shortest_chain("cat", "dog", ["cot", "cog", "dog"])        # 4
shortest_chain("pin", "pen", ["pan"])                      # 0   ("pen" isn't in the list)
shortest_chain("ab", "cd", ["cb", "ad", "cd"])             # 3

Constraints: words have 1 to 10 letters; words has up to 10,000 entries.

⭐ Bonus: a speed test with two lists of about 10,000 words earns a star in about O(N · L · 26) work (N words of length L). Comparing every pair of words to find which are one change apart is too slow for it.

Show hint

Treat words as nodes and single-letter changes as edges, then find the fewest steps from start. Don't build the edges up front: from a word, try each possible change and look the result up in a set, and cross words off once they've been reached.

Topic: BFS / multi-source BFS. Level-by-level search; seed the queue with every source.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc