Problem Statement

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 possible order.

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.

Examples

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".

Different Approaches

1️⃣ Unoptimized Approach

Intuition:

In this problem, all the possible transformations from the startWord to endWord must be found. Hence, in contrary to the previous problem, we do not stop the traversal on the first occurrence of endWord,but rather continue it for as many occurrences of the word as possible as we need all the shortest possible sequences in order to reach the end word.

Modification:

In the previous solution, whenever a word was matched from the given wordList, it was immediately erased from the Hashmap to avoid visiting it via a longer path. But since, here all the possible transformations must be returned, erasing it from the Hashmap might lose some of the possible transformations leading through it.

Thus, instead of erasing the word immediately when it is found, the erase/delete operation can be performed after the traversal for all the words for a particular level is completed allowing exploration of all the paths.

Understanding:

In order to form the different sequences for transformations in a particular level, the concept of Backtracking can be used.

• After adding the new word to a sequence, it is immediately removed (backtracked) to restore the sequence to its original state after the sequence is added to the queue.
• This backtracking step ensures that the original sequence can be used to try other possible transformations at the current level of the BFS.

Approach:

1. Use a queue for breadth-first search (BFS) to handle sequences of word transformations. Add all words from the word list to a set for quick lookup. Start with the initial word and add it to the queue.
2. Perform BFS level by level. For each word in the current level:
   1. Check if it matches the target word and add the sequence to the results. Generate all possible single-letter transformations.
   2. If a transformed word exists in the set, add it to the current sequence and push the sequence into the queue for further exploration.
   3. Mark words to be removed after the current level to prevent revisiting.
3. After adding a transformed word to the sequence, immediately remove it to restore the sequence for the next transformation.
4. Remove words marked during the level traversal from the set to prevent revisiting. Exit early if any sequences reaching the target word are found.
5. Return the list of resulting sequences.

Dry Run:

Code:

class Solution {
public:
    vector<vector<string>> findSequences(string beginWord, string endWord, vector<string> &wordList) {
        // Create a set for quick look-up of words available for transformation.
        set<string> wordSet(wordList.begin(), wordList.end());

        // Get the length of the words.
        int wordLength = beginWord.length();

        // Queue to store paths (each path is a sequence of words).
        queue<vector<string>> wordQueue;
        // Initialize the queue with the starting word.
        wordQueue.push({beginWord});

        // This will store all the valid transformation sequences that reach endWord.
        vector<vector<string>> sequences;

        // Temporary vector to keep track of words used at the current level that need to be removed from wordSet.
        vector<string> wordsToRemove;

        // Process the queue level by level (BFS).
        while (!wordQueue.empty()) {
            // Record the number of paths to process in the current BFS level.
            int levelSize = wordQueue.size();

            // Process each path in the current level.
            for (int i = 0; i < levelSize; i++) {
                // Get the current transformation sequence.
                vector<string> currentPath = wordQueue.front();
                wordQueue.pop();

                // Get the last word in the current path, which is the current word.
                string currentWord = currentPath.back();

                // If we've reached the end word, store the complete transformation sequence.
                if (currentWord == endWord) {
                    sequences.push_back(currentPath);
                    // We continue processing other paths at this level,
                    // because we want all shortest sequences.
                    continue;
                }

                // Try changing every character of the current word.
                for (int pos = 0; pos < wordLength; pos++) {
                    // Create a temporary word to try transformations.
                    string transformedWord = currentWord;
                    // Try all possible characters at position 'pos'.
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        transformedWord[pos] = ch;

                        // If the transformed word is in the wordSet, it's a valid next step.
                        if (wordSet.find(transformedWord) != wordSet.end()) {
                            // Create a new path that extends the current path with the transformed word.
                            vector<string> newPath = currentPath;
                            newPath.push_back(transformedWord);
                            // Enqueue the new path for further exploration.
                            wordQueue.push(newPath);
                            // Mark the transformed word for removal after processing this level.
                            wordsToRemove.push_back(transformedWord);
                        }
                    }
                }
            }

            // Remove all words used in the current level from the wordSet.
            // This prevents cycles and ensures we only consider the shortest paths.
            for (const string &word : wordsToRemove) {
                wordSet.erase(word);
            }
            // Clear the list for the next level.
            wordsToRemove.clear();
        }
        return sequences;
    }
};

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.
  • Each word is enqueued and dequeued at most once, leading to O(N) queue operations.
  • Checking if a word exists in the set and removing a word from the set takes O(1) on average. If there are N words, there are O(N) set operations.
  • 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*M)
  • A HashSet is used to store words in wordList taking O(N) space. In the worst case, the queue will store all possible sequences leading to a space requirement of O(N*M). Storing the result in a list will take O(N*M) space.