Question

22.7 Lab: Word ladder

Write a word ladder program. Read this wikipedia article that describes what a word ladder is: Word Ladder Your program must use a list to store the dictionary of words and then use stacks of strings and a queue of these stacks to solve for and output the word ladder. You are required to use the Standard Template Library (STL) list, stack, and queue. You must implement the WordLadder class. The class is declared in WordLadder.h. You may not add any data members or add any public member functions to this class. You will most likely want to add private helper functions though. Algorithm for finding a word ladder create a Stack containing just the first word in the ladder enqueue this Stack on to a Queue of Stacks while this Queue of Stacks is not empty get the word on top of the front Stack of this Queue for each word in the dictionary if the word is off by just one letter from the top word create a new Stack that is a copy of the front Stack and push on this off-by-one word found if this off-by-one word is the end word of the ladder, this new Stack contains the entire word ladder. You are done! otherwise, enqueue this new Stack and remove this word from the dictionary dequeue this front stack if the Queue is empty and you didn't find the word ladder, a word ladder does not exist for these 2 words

Answer 1

The screenshots of code implementing the wordLadder class along with output generated corresponding to a few test cases are attached below:

The C++ code is given below. The wordLadder class has been implemented using queue of stack of strings as mentioned in question. This class may be moved to separate .h file as per the needs.

#include <bits/stdc++.h>

using namespace std;

// put this class in WordLadder.h

class WordLadder{

list<string> dictionary;

//only constructor is public

public:

WordLadder(list<string> dictionary,const string &start, const string &end){

this->dictionary=dictionary;

output(start,end);

}

private:

// helper function

// implements algorithm

void output(const string &start, const string &end)

{

stack<string> words;

words.push(start);

queue<stack<string>> ladder;

ladder.push(words);

dictionary.remove(start);

while (!ladder.empty()) {

for (list<string>::iterator i = dictionary.begin(); i != dictionary.end(); ++i){

if (Differ_by_one(*i, ladder.front().top())){

if (*i == end){

stack<string> output;

while (!ladder.front().empty()){

output.push(ladder.front().top());

ladder.front().pop();

}

while (!output.empty()){

cout << output.top() << " ";

output.pop();

}

cout << *i <<endl;

return;

}

else{

stack<string> temp = ladder.front();

temp.push(*i);

ladder.push(temp);

i = dictionary.erase(i);

}

}

}

ladder.pop();

}

cout << "No word ladder exists for the pair of words '" <<start<<"' & '"<<end<<"'"<< endl;

}

//checks if the two strings differ by just one character

bool Differ_by_one(const string &dictionaryWord, const string &stackWord){

int count = 0;

for (int i = 0; i < stackWord.size(); ++i)

if (dictionaryWord.at(i) != stackWord.at(i))

++count;

if (count <= 1)

return true;

return false;

}

};

//=================class ends================

//testing in main

int main() {

//testing

list<string>dict;

dict.push_back("pot");

dict.push_back("hat");

dict.push_back("top");

dict.push_back("hot");

dict.push_back("hop");

dict.push_back("pat");

WordLadder(dict,"hot","top");

WordLadder(dict,"pot","top");

WordLadder(dict,"pat","top");

return 0;

}