839. Minimum Steps
0
Hard
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 an integer N, representing the length of the dictionary. The next N lines will contain the words in the dictionary.
Output Format
Output the minimum number of steps required to reach the end string.
Example
Input
hit cog
6
hot
dot
dog
lot
log
cog
Output
5
Constraints
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.
Initial String Length == End String Length
1 <= Dictionary Size <= 5000
Dictionary[i].length ==Initial String Length
All the words in Dictionary are unique.
Loading...
View Submissions
Console