Word ladder II
Amazon
CiscoThe problem
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.
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".
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".
Input: startWord = "abc", targetWord = "xyz", wordList = ["abc", "ayc", "ayz", "xyz"]
- N= Number of Words
- M= Length of Word
- 1 ≤ N ≤ 100
- 1 ≤ M ≤ 10
cpp
class Solution{
public:
vector<vector<string>> findSequences(string beginWord, string endWord,
vector<string> &wordList) {
}
};java
class Solution {
public List<List<String>> findSequences(String beginWord, String endWord, List<String> wordList) {
}
}python
class Solution:
def findSequences(self, beginWord, endWord, wordList):javascript
class Solution {
findSequences(beginWord, endWord, wordList) {
}
}csharp
class Solution{
public IList<IList<string>> FindSequences(string beginWord, string endWord, IList<string> wordList {
}
}go
func findSequences(beginWord string, targetWord string, wordList []string) [][]string {
}Stuck? Show a way to structure it+
- 01Run level-order BFS and record minimum distance
- 02Keep every valid parent from the previous level
- 03Stop expanding below the first target level
- 04Backtrack through parent lists to build all paths
Reference answer
Then expect these follow-ups
How do you control output explosion?
Tests: follow-up reasoning
Could bidirectional search reduce the BFS work?
Tests: follow-up reasoning
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question