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,goaland everything inwords) have the same length and use lowercase lettersa-z. - A step changes the letter at exactly one position; letters never move, and nothing is added or removed.
start != goal.wordsmay contain duplicates and may containstart.
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.