295. Word ladder II
Given two distinct words startWord and targetWord, and a list denoting wordList of unique words of equal lengths. Find all shortest transformation sequence(s) from startWord to targetWord. You can return them in any order possible.
In this problem statement, we need to keep the following conditions in mind:
A word can only consist of lowercase characters.
Only one letter can be changed in each transformation.
Each transformed word must exist in the wordList including the targetWord.
startWord may or may not be part of the wordList.
Return an empty list if there is no such transformation sequence.
Example 1:
Input: startWord = "der", targetWord = "dfs", wordList = ["des", "der", "dfr", "dgt", "dfs"]
Output: [ [ “der”, “dfr”, “dfs” ], [ “der”, “des”, “dfs”] ]
Explanation: The length of the smallest transformation sequence here is 3.
Following are the only two shortest ways to get to the targetWord from the startWord :
"der" -> ( replace ‘r’ by ‘s’ ) -> "des" -> ( replace ‘e’ by ‘f’ ) -> "dfs".
"der" -> ( replace ‘e’ by ‘f’ ) -> "dfr" -> ( replace ‘r’ by ‘s’ ) -> "dfs".
Example 2:
Input: startWord = "gedk", targetWord= "geek", wordList = ["geek", "gefk"]
Output: [ [ “gedk”, “geek” ] ]
Explanation: The length of the smallest transformation sequence here is 2.
Following is the only shortest way to get to the targetWord from the startWord :
"gedk" -> ( replace ‘d’ by ‘e’ ) -> "geek".
Now Your Turn!
Pick the correct output for the given inputInput: startWord = "abc", targetWord = "xyz", wordList = ["abc", "ayc", "ayz", "xyz"]
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- N= Number of Words
- M= Length of Word
- 1 ≤ N ≤ 100
- 1 ≤ M ≤ 10