Problem Statement

Given are the two distinct words startWord and targetWord, and a list of size N, denoting wordList of unique words of equal size M. Find the length of the shortest transformation sequence from startWord to targetWord.

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.

Note: If there’s no possible way to transform the sequence from startWord to targetWord return 0.

Examples

Example 1:

Input: wordList = [
                   "des",
                   "der",
                   "dfr",
                   "dgt",
                   "dfs"
                  ],
        startWord = "der", targetWord = "dfs"
Output: 3

Explanation: The length of the smallest transformation sequence from "der" to "dfs" is 3.
"der" -> (replace 'e' by 'f') -> "dfr" -> (replace 'r' by 's') -> "dfs".
So, it takes 3 different strings for us to reach the targetWord. Each of these strings are present in the wordList.

Example 2:

Input: wordList = [
                   "geek",
                   "gefk"
                  ],
      startWord = "gedk", targetWord = "geek"
Output: 2

Explanation: The length of the smallest transformation sequence from "gedk" to "geek" is 2.
"gedk" -> (replace 'd' by 'e') -> "geek".
So, it takes 2 different strings for us to reach the targetWord. Each of these strings are present in the wordList.

Different Approaches

How to Identify this as a graph problem?

Consider the following example:

It can be seen that in order to find the shortest transformation sequence, the level wise fashion helps in determining the shortest steps to go from startWord to targetWord.

Thus, a BFS-traversal will come in use for this problem making it a graph problem.

Understanding:

The levels of the transformation comprises of the words that can be formed from the words of the previous level (by changing only one letter). Thus, the BFS traversal can be performed starting from the startWord, exploring every possible word that can be made by changing one letter during each transformation.

Now consider the following example:

The first thing that needs to be done is that all the possible transformations from a given word needs to be generated. Out of all the possible words generated, the transformation can be done in only those words which are present in the wordList. Now to check whether a word exists in the wordList or not, a set data structure can be used, which can help find answer this query in O(1) time.

Observation:

Consider a scenario where word "hit" also exist in the wordList and is transformed to "hot" and in the next transformation converted back to "hit". To avoid such unnecessary transformations, once a word is found, it can be deleted from the set which is also a O(1) operation.
The deletion operation is safe because when a word is found via the shortest transformations, there is no use of finding it again through some other path requiring more transformations.

Approach:

1. Use a queue to store pairs of words and their corresponding transformation steps. Start with the initial word and step count of 1.
2. Convert the word list into a hash set for efficient word existence checks and removal operations.
3. While the queue is not empty:
   1. Extract the current word and its step count.
   2. If the current word matches the target word, return the step count.
4. For each character in the current word, change it to every letter from 'a' to 'z'. For each transformation:
   1. Check if the new word is in the hash set.
   2. If found, remove it from the set, marking it as visited, and add it to the queue with an incremented step count.
   3. If the queue is exhausted without finding the target word, return 0.

Key Points:

• BFS ensures the shortest path by exploring all nodes level by level.
• Hash set enables O(1) lookups and deletions, making the process efficient.
• The algorithm returns the shortest transformation sequence length or 0 if no valid sequence exists.

Code:

class Solution {
public:
    int wordLadderLength(string startWord, string targetWord, vector<string> &wordList) {
        // If the target word is not present in the word list, no valid transformation exists.
        if(find(wordList.begin(), wordList.end(), targetWord) == wordList.end())
            return 0;
        
        // Queue to hold pairs of (current word, transformation distance).
        queue<pair<string, int>> wordQueue;
        
        // Get the length of the words (assuming all words are the same length).
        int wordLength = startWord.length();
        
        // Insert words from the word list into a set for fast lookup.
        set<string> wordSet(wordList.begin(), wordList.end());
        
        // Enqueue the start word with an initial distance of 1.
        wordQueue.push({startWord, 1});
        
        // Process the queue until it's empty.
        while(!wordQueue.empty()) {
            // Retrieve and remove the front element from the queue.
            pair<string, int> front = wordQueue.front();
            wordQueue.pop();
            
            string currentWord = front.first;
            int currentDistance = front.second;
            
            // If the current word is the target word, return the current transformation distance.
            if (currentWord == targetWord) {
                return currentDistance;
            }
            
            // For each position in the current word...
            for (int i = 0; i < wordLength; i++) {
                // Create a temporary word for transformation.
                string tempWord = currentWord;
                // Try replacing the character at position i with every letter from 'a' to 'z'.
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    tempWord[i] = ch;
                    
                    // If the new word exists in the set, it's a valid transformation.
                    if (wordSet.find(tempWord) != wordSet.end()) {
                        // Enqueue the valid transformation with an incremented distance.
                        wordQueue.push({tempWord, currentDistance + 1});
                        // Remove the word from the set to prevent reprocessing.
                        wordSet.erase(tempWord);
                    }
                }
            }
        }
        // If no transformation sequence leads to the target, return 0.
        return 0;
    }
};

Complexity Analysis:

• Time Complexity:O(N*M*26)
  • In the worst case, the steps required to reach from startWord to targetWord can go up to N. During each step, all the characters for the word are replaced from 'a' to 'z' taking O(M*26) time.
  • Adding all the words in wordList takes O(N) time.
  • Note: If an ordered set is used in place of an unordered set then there will be a logN factor adding to the time complexity, since delete and update operations take O(logN) time for the ordered set.
• Space Complexity:O(N)
  • A Hashset is used to store words in wordList taking O(N) space.