Word Ladder

Problem Overview
The Word Ladder problem (LeetCode 127) asks to find the shortest transformation sequence length from beginWord to endWord using a given wordList, where each step changes one letter and the new word must exist in wordList. It leverages BFS for shortest path, Hash Table (set for O(1) lookups), and String manipulation.[1][3]

Full Problem Statement

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

• A transformation sequence from word1 to word2 is valid if:
  • They have the same length.
  • Differ by exactly one character.
  • The intermediate words (excluding beginWord and endWord) must exist in wordList.
• beginWord does not need to be in wordList.
• endWord must be in wordList (otherwise, return 0).
• The sequence length includes beginWord and endWord.[3][9][1]

Input/Output Examples

| Example | beginWord | endWord | wordList | Output | Explanation | |---------|-----------|---------|---------------------------|--------|-------------| | 1 | "hit" | "cog" | ["hot","dot","dog","lot","log","cog"] | 5 | One shortest sequence: hit → hot → dot → dog → cog. [1] | | 2 | "hit" | "cog" | ["hot","dot","dog","lot","log"] | 0 | endWord "cog" not in wordList. [1] |

Additional Notes on Examples:

• Sequence "hit → hot → lot → log → cog" also works (length 5).
• BFS ensures shortest path by level-order traversal.[1][3]

Constraints

• 1 ≤ beginWord.length ≤ 10
• beginWord.length === endWord.length
• wordList[i].length === beginWord.length for all i
• 1 ≤ wordList.length ≤ 5000
• Characters are lowercase English letters ('a'-'z').
• beginWord ≠ endWord
• All words have the same length.[3][1]