wAnswer in C++ only using files: main.cpp and WorldLadder.cpp 22.7 Lab: Word lad

Question

wAnswer in C++ only using files: main.cpp and WorldLadder.cpp

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 dictionaryif 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

WorldLadder.h is provided below:

#ifndef WORDLADDER_H_
#define WORDLADDER_H_

#include <string>
#include <list>
#include <stack>
#include <queue>
#include <ostream>

using std::string;
using std::list;
using std::queue;
using std::stack;
using std::ostream;

class WordLadder {

//member data fields
private:
list<string> dict;  //list of possible words in ladder

//public member functions
public:
WordLadder(const string &listFile);
void outputLadder(const string &, const string &, const string &);

//private member functions
private:
bool offByOne(const string &s1, const string &s2) const;
bool findLadder(stack<string> &s, const string &end);
void output(stack<string> &, ostream &) const;
};
#endif /*WORDLADDER_H_*/

Explanation / Answer

Solution:

#ifndef WORDLADDER_H_
#define WORDLADDER_H_

#include <string>
#include <list>
#include <stack>
#include <queue>
#include <ostream>

using std::string;
using std::list;
using std::queue;
using std::stack;
using std::ostream;

class WordLadder {

void WordLadder::outputLadder(const string &start, const string &end)
{
stack<string> words;
words.push(start);

queue<stack<string>> ladder;
ladder.push(words);

while (!ladder.empty())
{
for (list<string>::iterator i = dictionary.begin(); i != dictionary.end(); ++i)
{
if (oneDiff(*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 this word." << endl;
}

bool WordLadder::oneDiff(const string &dictWord, const string &stackWord)
{
int count = 0;

for (int i = 0; i < stackWord.size(); ++i)
{
if (dictWord.at(i) != stackWord.at(i))
{
++count;
}
}

if (count <= 1)
{
return true;
}

return false;
}

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.