Given two words word1 and word2 , and a dictionary's Dict , write a program to find the length of the shortest transformation sequence from word1 to word2 , such that:

• Adjacent words in the chain only differ by one character.
• Each transformed word must exist in the dictionary. Note that word1 is not a transformed word but word2 must be in the Dict .

Problem Note

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume word1 and word2 are non-empty and are not the same.

Example 1

Input: word1 = "fit", word2 = "dog", 
Dict = ["hit","hot","cot","dog","dot","log","cog"]
Output: 5
Explanation: As one shortest transformation is:
"fit"->"hit"->"hot"->"dot"->"dog"
Return its length which is 5. 
Notice "fit" is not in Dict but "dog" is.

Example 2

Input: word1 = "fool", word2 = "sage", 
Dict = ["cool","pool","poll","foil","fail","pole", "pope", "pale", "page", "sage", "sale", "fall"]

Output: 7
Explanation: As one shortest transformation is :
"fool"->"pool"->"poll"->"pole"->"pale"->"page"->"sage", Return its length which is 7.