#include #include #include

using namespace std;

bool checkforTransformation(string s1, string s2) { if(s1.size()!=s2.size()) return false; // Assuming string has only small case alphabetical characters int count_S1[26], count_S2[26];

// Initializing all elements to 0 for(int i=0;i

// Counting the frequency of all letters in string s1 for(char c:s1) { count_S1[c-'a'] += 1; } // Counting the frequency of all letters in string s2 for(char c:s2) { count_S2[c-'a'] += 1; }

// If frequency of all letters (even the letters with frequency 0) match exactly in both words, // then the two words are transformable from one another for(int i=0;i

return true; }

// Function to determine if one word results from another by swapping an adjacent pair of letters bool checkForAdjacentSwapping(string s1, string s2) { // If the two string are not of same length, they can't be formed from each other // If two strings are same, they can't be formed from each other using an adjacent letters swapping swapping if(s1.size()!=s2.size() || s1==s2) return false; int n=s1.size(), next=-1;

// Check for the swapped adjacent letters for(int i=0;i

// Making sure that the letters occuring after adjacent letters swapping matches exactly for(int i=next;i

return true; }

void generateProofSequence(string s1, string s2) { /** LOGIC : * Find the letter in the first word matching with the first letter of the second word. * Swap it with the left adjacent letters iteratively until it reaches at the 0th index * Now, the first letter of both the words are matching. * * Repeat the above process for each subsequent letters till you have completely transformed * the first word to the second */

cout=i;j--) { char temp = s1[j+1]; s1[j+1] = s1[j]; s1[j] = temp; cout

cout

bool checkProofSequence(string s, string s1, string s2) { string word1="", word2=""; int i=0;

// retrieve the first word for(i=0;i

// retrieved first word must match with the actual given first word, i.e. s1 if(word1 != s1) { return false; }

// Match if the next words are a result of exactly one Ajacent Swapping of letters for(int j=i+1;j

// last word must be an Adjacent Swapping of its prevvious word if(!checkForAdjacentSwapping(word1, word2)) { return false; } // retrieved last word must match exactly with the given second word, i.e. s2 if(word2 != s2) { cout

return true; }

int main() { string words[][2] = {{"tops", "spot"},{"atom", "bomb"},{"meals", "males"},{"saint", "satin"},{"avenge", "geneva"},{"meals", "salem"},{"sales", "seals"},{"balm", "lamb"},{"mean", "mane"},{"salts", "lasts"},{"blot", "bolt"},{"melon", "lemon"},{"blow", "bowl"},{"moist", "omits"},{"sharp", "harps"},{"brag", "grab"},{"more", "rome"},{"shrub", "brush"},{"chum", "much"},{"needs", "dense"},{"siren", "rinse"},{"coal", "cola"},{"nerved", "denver"},{"skids", "disks"},{"counts", "tucson"},{"none", "neon"},{"skill", "kills"},{"nude", "dune"},{"snail", "nails"},{"diary", "dairy"},{"ocean", "canoe"},{"sober", "robes"},{"domains", "madison"},{"pace", "cape"},{"soils", "oil"}};

int n= sizeof(words)/sizeof(words[0]);

int index=0, points_earned=0; bool isAnagram; char choice; string word1, word2, input; while(true && index

word1 = words[index][0]; word2 = words[index1][1];

cout>choice; cout

isAnagram = checkforTransformation(word1, word2); if(choice == 'Y' || choice == 'y') { cout>input; if(checkProofSequence(input, word1, word2)) { cout

index++;

cout

cout Modify your program created in the previous question so that it keeps lists of intermediate words during the swaps instead of keeping lists of swap indices. computer before submitting it to make sure your peers will be able to open, extract, compile and test your program. Modify your program created in the previous question so that it keeps lists of intermediate words during the swaps instead of keeping lists of swap indices. computer before submitting it to make sure your peers will be able to open, extract, compile and test your program

<>

<>

<-1>