446. Minimum Steps



Parth and Varun are playing a game where they need to transform an initial string into an end string using a dictionary. The transformation sequence is a sequence of words starting from the initial string and ending with the end string, where each adjacent pair of words differs by a single letter. The words in the sequence must be present in the dictionary. Given the initial string, end string, and the dictionary, you need to determine the minimum number of steps required to reach the end string from the initial string. If no such sequence exists, return 0.

Input Format

The first line of input will contain the initial string and the end string separated by a space. The second line will contain the length of the dictionary, denoted by 'N'. The following 'N' lines will contain the words in the dictionary.

Output Format

Output the minimum number of steps required to reach the end string.



hit cog 6 hot dot dog lot log cog




1 <= Initial String Length <= 10
Initial String Length == End String Length
1 <= Dictionary Size <= 5000
Dictionary[i].length ==Initial String Length
All the words in Dictionary are unique.

View Submissions