75. Word Ladder

Hard · Graph

A word ladder is a sequence of words where each word differs from the previous one by exactly one letter. Given a start word, an end word, and a list of valid words, find the shortest word ladder that transforms the start word into the end word. Every intermediate word in the sequence must be in the provided word list. Return the total number of words in the shortest sequence (including both the start and end words). If no valid transformation exists, return 0.

Examples

Example 1
Input: ["hit","cog",["hot","dot","dog","lot","log","cog"]]
Output: 5
Explanation: hit→hot→dot→dog→cog
Example 2
Input: ["hit","cog",["hot","dot","dog","lot","log"]]
Output: 0
Explanation: endWord not in list

Constraints