Given two distinct words startWord and targetWord, along with a list wordList containing unique words of equal length, find the length of the shortest transformation sequence from start word to target word.
Only one character can change in one move. Every transformed word must exist in wordList. If no valid transformation sequence exists, return 0.
Example 1
Input: startWord = "der", targetWord = "dfs", wordList = ["des","der","dfr","dgt","dfs"]
Output: 3
Explanation: The shortest valid sequence is der -> dfr -> dfs, so sequence length is 3.
Example 2
Input: startWord = "gedk", targetWord = "geek", wordList = ["geek","gefk"]
Output: 2
Explanation: One character change converts gedk to geek, so sequence length is 2.
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.
Now the task becomes finding the shortest path from startWord to targetWord in this graph. Since each transformation has the same cost, BFS is used because it explores all shorter sequences before moving to longer ones.
A hash set stores unused dictionary words for average O(1) lookup. Removing a generated word immediately after discovery prevents duplicate queue entries and repeated processing.
Algorithm
Initialize a hash set with all words from
wordListand return0whentargetWordis absent, as no valid sequence can end at the target.Add
{startWord, 1}to a queue and removestartWordfrom the set, establishing the first sequence level while preventing rediscovery.Continue BFS while the queue contains states and remove the front word with the corresponding sequence length.
Return the stored sequence length when the removed word equals
targetWord, as BFS reaches words in increasing transformation distance.For every character position, store the original character and replace the position with each letter from
'a'to'z', generating every possible one-character transformation.For every generated word found in the set, remove the word immediately and enqueue the word with
steps+1; restore the original character after processing the position.Return
0when the queue becomes empty without reachingtargetWord, indicating that no valid transformation sequence exists.
Dry Run
Word Ladder
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Return length of the shortest valid transformation sequence. int wordLadderLength(string startWord, string targetWord, vector<string>& wordList) { unordered_set<string> dictionary(wordList.begin(), wordList.end()); // Missing target makes transformation impossible. if (dictionary.find(targetWord) == dictionary.end()) { return 0; } queue<pair<string, int>> q; // Start word has sequence length one. q.push({startWord, 1}); dictionary.erase(startWord); // BFS explores shorter transformations before longer transformations. while (!q.empty()) { string word = q.front().first; int steps = q.front().second; q.pop(); // Reaching target gives minimum sequence length. if (word == targetWord) { return steps; } // Try changing every position of current word. for (int pos = 0; pos < (int)word.size(); pos++) { char original = word[pos]; // Try every lowercase letter at selected position. for (char ch = 'a'; ch <= 'z'; ch++) { word[pos] = ch; // Valid unseen word becomes next BFS state. if (dictionary.find(word) != dictionary.end()) { dictionary.erase(word); q.push({word, steps + 1}); } } // Restore original character before next position. word[pos] = original; } } return 0; }};// Driver code.int main() { string startWord = "der"; string targetWord = "dfs"; vector<string> wordList = {"des", "der", "dfr", "dgt", "dfs"}; Solution sol; cout << sol.wordLadderLength(startWord, targetWord, wordList); return 0;}Complexity Analysis
Time Complexity: O(N*L*26*L), where N is the number of dictionary words and L is the word length; every position tries 26 letters and forms or hashes a length-L word.
Space Complexity: O(N*L), where the hash set and BFS queue can store up to N words of length L.
Interview follow-up Questions
BFS explores transformations by increasing sequence length, so the first target reach gives shortest length.
Be the first to add a comment.