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.``````