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