131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    
    /* Function to determine number of steps
    to reach from start ward to target word */
    vector<vector<string>> findSequences(string beginWord, string endWord,
                                         vector<string> &wordList) {
        // To store the answer
        vector<vector<string>> ans;
        
        /* Queue data structure to store 
        the sequence of transformations */
        queue <vector<string>> q;
        
        // Add all the words to a hashset
        unordered_set<string> st(wordList.begin(), 
                                 wordList.end());
        
        // Add the sequence containing starting word to queue
        q.push({beginWord});
        
        // Erase starting word from set if it exists
        st.erase(beginWord);
        
        /* Set to store the words that must be deleted 
        after traversal of a level is complete */
        unordered_set <string> toErase;
        
        // Until the queue is empty
        while(!q.empty()) {
            
            // Size of queue
            int size = q.size();
            
            // Traversing all words in current level
            for(int i=0; i<size; i++) {
                
                // Sequence 
                vector<string> seq = q.front();
                
                // Last added word in sequence
                string word = seq.back();
                q.pop();
                
                // If the Last word same as end word
                if(word == endWord) {
                    // Add the sequence to the answer
                    if(ans.empty()) {
                        ans.push_back(seq);
                    }
                    else if(ans.back().size() == seq.size()) {
                        ans.push_back(seq);
                    }
                }
                
                // Iterate on every character
                for(int pos = 0; pos < word.length(); pos++){
                    
                    // Original letter
                    char original = word[pos];