676. Word Ladder — Shortest Transformation

Given beginWord, endWord, and a word list, transform beginWord into endWord by changing one letter at a time so that each intermediate word is in the list. Return the number of words in the shortest transformation sequence (including both endpoints), or 0 if none exists. The input is JSON {beginWord, endWord, wordList}.

Input: JSON {beginWord, endWord, wordList}.

Output: Integer — the shortest sequence length, or 0.

Examples

Input: {"beginWord":"hit","endWord":"cog","wordList":["hot","dot","dog","lot","log","cog"]}
Output: 5
Explanation: hit -> hot -> dot -> dog -> cog.

Input: {"beginWord":"hit","endWord":"cog","wordList":["hot","dot","dog","lot","log"]}
Output: 0
Explanation: endWord not reachable.

Input: {"beginWord":"a","endWord":"c","wordList":["a","b","c"]}
Output: 2
Explanation: a -> c directly.

Constraints

• 1<=word length<=10
• 0<=wordList<=5000

Asked by