Hints Break the problem into pieces and then solve each piec

Hints

Break the problem into pieces and then solve each piece. I suggest writing the code in the following steps:

? Read the words into a set (i.e. build the dictionary); Be able to test the set for a “word”

? Write a function that can generate the 5 letter sequences that are 1 letter different from a given

input; identify the sequences that actually words

? Generate a queue of stacks using hardcoded data

? Combine the above functionality to create word ladders

Solution

#include <iostream>
#include \"console.h\"
#include \"lexicon.h\"
#include \"queue.h\"
#include \"simpio.h\"
#include \"vector.h\"
#include \"filelib.h\"
using namespace std;

const string FILENAME = \"welcome\";

Vector<string> getLadder(string start, string end);
void printLadder(Vector<string> &ladder);
void getLexicon(Set<string> &lexicon);

int main() {
Vector<string> ladder;
string start, end;
  
while (true) {
   start = getLine(\"Enter Starting word : \");
   if (start.size() == 0) break;
   end = getLine(\"Enter ending word : \");
   cout << \"Searching please wait.........\" << endl;
  
   // if length of start and end are different then there is no word ladder
   if (start.size() != end.size())
   cout << \"No word ladder found\" << endl << endl;
   else {
   ladder = getLadder(start, end);
   printLadder(ladder);
   }
}
cout << \"End of the game!!!\" << endl;
return 0;
}

/* here I am using breadth-first search algorithm to return a ladder of words
starting from the string \"start\" upto the string \"end\"*/
Vector<string> getLadder(string start, string end) {
Set<string> lexicon;
getLexicon(lexicon);

//To store partial ladders
Queue< Vector<string> > ladderQ;
  
// To track current ladder
Vector<string> cl; // current ladder is represented as cl

// Set of words used to create ladder
Set<string> uw; // set of words is represented as uw

uw.add(start);
cl.add(start);
ladderQ.enqueue(cl);
  
while (!ladderQ.isEmpty()) {
   // get current ladder from top of the queue
   cl = ladderQ.dequeue();
   string lw = cl[cl.size() - 1]; // here lastword is represented as lw
  
   // check whether the last word in the ladder is destination wordor not
   if (lw == end)
   return cl;

   // add words in next hop to new ladders and add those ladders to bottom of the queue
   string newWord;
   for (int i = 0; i < lw.length(); i++) {
   for (char ch = \'a\'; ch <= \'z\'; ch++) {
       newWord = lw.substr(0, i) + ch + lw.substr(i+1);
       if (lexicon.contains(newWord) && (!uw.contains(newWord))) {
       Vector<string> newLadder = cl;
       newLadder.add(newWord);
       ladderQ.enqueue(newLadder);
       uw.add(newWord);
       }
   }
   }
}

// if no ladder built till destination word then return empty ladder
Vector<string> emptyLadder;
return emptyLadder;
}

// Reads a set of english words from file and add them to the \"lexicon\"
// here set of stringsare passed as argument.

void getLexicon(Set<string> &lexicon) {
ifstream infile;
string line;
if (!openFile(infile, FILENAME)) error(\"Error reading file.\");
while (true) {
   getline(infile, line);
   if (infile.fail()) break;
   lexicon.add(line);
}
}

// Below function Prints the \"ladder\"
void printLadder(Vector<string> &ladder) {
if (ladder.size() > 0) {
   for (int i = 0; i < ladder.size(); i++) {
   cout << ladder[i];
   if (i != ladder.size() - 1)
       cout << \" -> \";
   }
} else
   cout << \"No word ladder found.\";
cout << endl << endl;
}