Practice/Uber/Leetcode 127. Word Ladder

Leetcode 127. Word Ladder

CodingMust

Problem

You are given a starting word, a target word, and a dictionary of valid words. Your task is to find the shortest sequence of transformations from the starting word to the target word, where:

• Each transformation changes exactly one letter
• Every intermediate word (after each transformation) must exist in the dictionary
• All words have the same length

Return the total number of words in the shortest transformation sequence (including both the start and end words). If no valid transformation sequence exists, return 0.

Requirements

1. Each transformation must change exactly one character at a time
2. All intermediate words must be present in the provided word dictionary
3. The target word must be in the dictionary for a valid path to exist
4. Return the length of the shortest valid sequence, or 0 if impossible
5. All words have equal length and contain only lowercase letters

Constraints

• 1 ≤ beginWord.length ≤ 10
• endWord.length == beginWord.length
• 1 ≤ wordList.length ≤ 5000
• wordList[i].length == beginWord.length
• All strings consist of lowercase English letters
• beginWord, endWord, and all words in wordList are unique

Examples

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: One shortest transformation sequence is: hit -> hot -> dot -> dog -> cog This sequence contains 5 words.

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] Output: 0 Explanation: The endWord "cog" is not in the dictionary, so no transformation is possible.

Example 3:

Input: beginWord = "cat", endWord = "hat", wordList = ["hat"] Output: 2 Explanation: cat -> hat (2 words in the sequence)