269. Word Ladder (Shortest Transformation Length)

Given begin word, end word, and a word list, return the number of words in the shortest transformation sequence from begin to end, changing one letter at a time, where each intermediate word must be in the list. Return 0 if no sequence exists. Input: JSON {begin, end, words}.

Input: JSON {begin, end, words}.

Output: Integer — sequence length or 0.

Examples

Input: {"begin":"hit","end":"cog","words":["hot","dot","dog","lot","log","cog"]}
Output: 5
Explanation: hit->hot->dot->dog->cog.

Input: {"begin":"hit","end":"cog","words":["hot","dot","dog","lot","log"]}
Output: 0
Explanation: 'cog' not in list.

Constraints

• 1<=word.length<=10
• 1<=words.length<=5000
• all same length

Asked by