In this code will be responsible for implementing this function will return the conversion between s1 and s2, according to the lowest Lewis Carroll distance. The first element of the vector should be s1, the last s2, and each consecutive should be one letter apart. Each element should be a valid word (i.e. it is present in the words WordSet passed in). If there are two or more equally least Lewis Carrolldistance ways to convert between the two words, you may return any of them. If there is no path between s1 and s2, return an empty vector. The behavior of this function is undefined (which means it won't be tested) for the case where s1 == s2. It is recommended that you compute the distance via a breadth-first search. To visualize this,imagine a graph where the words are vertices and two vertices share an (undirected) edge if they are one letter apart. You may use std::queue -- you do not need your own. A good thing to do the first time you see a word in the previous part is to place it into a std::unordered_map, where the key is the word you just saw and the value is the word that you saw immediately before it. This will allow you to later produce the path: you know the last word, and you know the prior word for each word in the path except the first. Furthermore, if the key isn't in that map, this tells you that you haven't seen it before.

hpp: #include

class Word { public: explicit WordSet(unsigned initialCapacity, unsigned evictionThreshold = DEFAULT_EVICT_THRESHOLD); ~WordSet();

void insert(const std::string & s);

bool contains(const std::string & s) const;

unsigned getCount() const;

unsigned getCapacity() const;

void remove(const std::string &s);

private: static constexpr unsigned BASE_H1 = 37; static constexpr unsigned BASE_H2 = 41; static constexpr unsigned DEFAULT_EVICT_THRESHOLD = 5;

std::string *t1; std::string *t2; unsigned capacity; unsigned count; unsigned ecount; unsigned evicthold; bool Prime(unsigned n); unsigned nextPrime(unsigned n); void resize(); };

CODE: #include #include #include "Word.hpp"

void loadWordsIntoTable(WordSet & words, std::istream & in);

std::vector< std::string > convert(const std::string & s1, const std::string & s2, const WordSet & words);