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. Comparing every pair of words to find which ones are one change apart is far too slow at this size: aim for about O(N · L · 26) work, where N is the number of words and L their length.
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.