Practice/Bloomberg/Leetcode 126. Word Ladder II

Leetcode 126. Word Ladder II

CodingMust

Problem

You are given a starting word, an ending word, and a dictionary of valid words. Each word has the same length. In one transformation step, you can change exactly one letter of a word to create a new word that must exist in the dictionary.

Find all shortest possible transformation sequences that convert the starting word into the ending word. Each sequence should contain only valid words from the dictionary (plus the starting word), and each consecutive pair of words should differ by exactly one letter.

If no transformation sequence exists, return an empty list. If multiple shortest sequences exist, return all of them.

Requirements

1. Return all shortest transformation sequences from beginWord to endWord
2. Each intermediate word (except beginWord) must be in the wordList
3. Each step must change exactly one letter
4. All sequences returned must have the same minimum length
5. The order of sequences in the result does not matter
6. Words in the wordList are unique

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
• All words in wordList are unique

Examples

Example 1:

` Input: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log","cog"]

Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

Explanation: Two shortest transformation sequences exist:

• hit → hot → dot → dog → cog
• hit → hot → lot → log → cog Both have length 5. `

Example 2:

` Input: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"]

Output: []

Explanation: The endWord "cog" is not in the dictionary, so no valid transformation exists. `

Example 3:

` Input: beginWord = "red" endWord = "tax" wordList = ["ted","tex","red","tax","tad","den","rex","pee"]

Output: [["red","ted","tad","tax"],["red","ted","tex","tax"],["red","rex","tex","tax"]]

Explanation: Three different shortest paths exist, all with the same length. `