Word Ladder

A transformation sequence changes exactly one letter at a time, and every intermediate word must exist in wordList. Return the number of words in the shortest valid sequence from beginWord to endWord, including both endpoints. If no sequence exists, return 0.

All words have the same length.

Input / output

• Input: beginWord: string, endWord: string, wordList: string[]
• Output: integer shortest ladder length, or 0 if impossible

Examples

1. beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] returns 5 for hit -> hot -> dot -> dog -> cog.
2. beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] returns 0.
3. beginWord = "lost", endWord = "cost", wordList = ["most","fist","lost","cost","fish"] returns 2.

Constraints

• 1 <= beginWord.length <= 10
• beginWord.length == endWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• Words contain only lowercase English letters

Target complexity

• Aim for breadth-first search over implicit graph neighbors, because the first time BFS reaches endWord, that path is guaranteed shortest.

Hints

1. Treat each word as a graph node, where edges connect words differing by exactly one letter.
2. You do not need to build every edge ahead of time; generate neighbors by changing one position at a time during BFS.

Follow-up What would a bidirectional BFS buy you here, and when is it worth the extra implementation complexity?