Loading...
Loading...
Loading...
You are given a start word, a target word and a list of allowed words, all the same length. In one move you change exactly one letter so that the new word is in the list. Print the number of words in the shortest sequence from the start word to the target word, counting both, or 0 if it is impossible. The start word need not be in the list.
Example 1
Input
hit cog 6 hot dot dog lot log cog
Output
5
hit, hot, dot, dog, cog is 5 words.
Example 2
Input
hit cog 5 hot dot dog lot log
Output
0
Try the problem first. Open one hint at a time.
Think of each word as a node and a one-letter change as an edge.
To find neighbours quickly, replace each letter by * and group words by the pattern, such as h*t.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor