Given two distinct words startWord and targetWord, along with a list wordList containing unique words of equal length, return all shortest transformation sequences from start word to target word.
Only one character can change in one move. Every transformed word must exist in wordList. If no valid shortest sequence exists, return an empty list.
Example 1
Input: startWord = "der", targetWord = "dfs", wordList = ["des","der","dfr","dgt","dfs"]
Output: [["der","dfr","dfs"],["der","des","dfs"]]
Explanation: Both sequences have length 3, and no shorter valid sequence exists.
Example 2
Input: startWord = "gedk", targetWord = "geek", wordList = ["geek","gefk"]
Output: [["gedk","geek"]]
Explanation: A direct one-character change reaches the target word.
Approach
If two words differ by only one character, one word can be transformed into the other in a single move. This relation creates the graph idea: every word becomes a node, and an edge exists between two words if they differ by exactly one character.
All parents reaching the same word from the preceding level must be preserved. Delaying dictionary removal until a complete level finishes allows multiple shortest parents, while DFS backtracking reconstructs every shortest sequence from the target to the start.
Algorithm
Initialize a dictionary set from
wordListand return an empty list whentargetWordis absent, since no valid sequence can reach the target.Initialize the current BFS level with
startWordand create a parent map for storing every shortest predecessor of each generated word.Before expanding a level, remove all current-level words from the dictionary together, preventing longer revisits while preserving multiple parents discovered within the same level.
For every current-level word, generate all one-character transformations by replacing each position with letters from
'a'to'z'.For every generated word still present in the dictionary, record the current word as a parent and add the generated word to the next-level set.
Finish processing the complete level containing
targetWord, then stop BFS because all shortest parent relationships have been collected.Run DFS from
targetWordthrough the parent map, reverse every path reachingstartWord, add each sequence to the answer, and return all sequences.
Dry Run
word Ladder II
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Build paths from target back to start using parent links. void dfs(string word, string& startWord, unordered_map<string, vector<string>>& parents, vector<string>& path, vector<vector<string>>& answer) { // Start word closes one shortest sequence. if (word == startWord) { vector<string> sequence = path; reverse(sequence.begin(), sequence.end()); answer.push_back(sequence); return; } // Try every parent from previous BFS level. for (string& parent : parents[word]) { path.push_back(parent); dfs(parent, startWord, parents, path, answer); path.pop_back(); } }public: // Return all shortest transformation sequences. vector<vector<string>> findSequences(string startWord, string targetWord, vector<string>& wordList) { unordered_set<string> dictionary(wordList.begin(), wordList.end()); vector<vector<string>> answer; // Missing target makes transformation impossible. if (dictionary.find(targetWord) == dictionary.end()) { return answer; } unordered_map<string, vector<string>> parents; unordered_set<string> currentLevel; currentLevel.insert(startWord); dictionary.erase(startWord); bool found = false; // BFS builds only shortest-level parent links. while (!currentLevel.empty() && !found) { unordered_set<string> nextLevel; // Remove all words discovered at current depth together. for (string word : currentLevel) { dictionary.erase(word); } // Expand every word from current BFS level. for (string word : currentLevel) { string changed = word; // Try each character position. for (int pos = 0; pos < (int)changed.size(); pos++) { char original = changed[pos]; // Try every lowercase replacement. for (char ch = 'a'; ch <= 'z'; ch++) { changed[pos] = ch; // Valid unseen word belongs to next level. if (dictionary.find(changed) != dictionary.end()) { nextLevel.insert(changed); parents[changed].push_back(word); if (changed == targetWord) { found = true; } } } // Restore original character before next position. changed[pos] = original; } } currentLevel = nextLevel; } // No shortest path was found. if (!found) { return answer; } vector<string> path = {targetWord}; dfs(targetWord, startWord, parents, path, answer); return answer; }};// Driver code.int main() { string startWord = "der"; string targetWord = "dfs"; vector<string> wordList = {"des", "der", "dfr", "dgt", "dfs"}; Solution sol; vector<vector<string>> ans = sol.findSequences(startWord, targetWord, wordList); // Print every shortest sequence. for (auto& sequence : ans) { for (string& word : sequence) { cout << word << " "; } cout << endl; } return 0;}Complexity Analysis
Time Complexity: O(N×L×26×L+P×L), where N is the dictionary size, L is the word length, and P is the total number of word occurrences across all returned sequences.
Space Complexity: O((N+M+P)×L), where M is the number of stored parent links; the dictionary, BFS levels, parent map, recursion paths, and output store length-L words.
Interview follow-up Questions
Delayed removal allows multiple shortest parents from the same level to connect to one child word.
Be the first to add a comment.