Given a start word, an end word, and a list of allowed words (all of the same length), find the length of the shortest transformation sequence start -> ... -> end where each step changes exactly one letter and every word after start must be in the allowed list (the end word must also be in the list). The length is the number of words in the sequence, counting both endpoints. If no such sequence exists, output 0.
If start equals end, the sequence is just the single word, so the answer is 1.
Line 1: the start word.
Line 2: the end word.
Line 3: an integer W, the number of allowed words.
Next W lines: the allowed words (all the same length as start).
One line: the length of the shortest transformation sequence, or 0 if none exists.
Example 1
Input
hit cog 6 hot dot dog lot log cog
Expected
5
Explanation
hit -> hot -> dot -> dog -> cog is 5 words, the shortest such chain.
Example 2
Input
hit cog 3 hot dot dog
Expected
0
Explanation
'cog' is not in the allowed list, so no sequence can end at it: 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →