In C++

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

For testing you can download a dictionary of 5-letter words from: https://docs.google.com/document/d/1cJddckLAI6SdHUm7VC3OYo_LYq_3QeJLVIYbY0rlXWY/edit

Given WordLadder.h (need to create from scratch WordLadder.cpp and main.cpp)

#ifndef WORDLADDER_H_

#define WORDLADDER_H_

#include

#include

#include

#include

#include

using std::string;

using std::list;

using std::queue;

using std::stack;

using std::ostream;

class WordLadder {

//member data fields

private:

list 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 &s, const string &end);

void output(stack &, ostream &) const;

};

#endif /*WORDLADDER_H_*/