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 butword2
must be in theDict
.
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
andword2
are nonempty 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.