Word Ladders The game of word ladders was invented by Lewis

Word Ladders The game of word ladders was invented by Lewis Carroll in 1878 during Christmas vacation when he apparently had too much time on his hands. The game is really quite simple: the player must find a way to transform one English word into another by successively changing only a single letter. At each stage the intermediate values must also be English words. For example, the word jump may be transformed into the word play through the transformations jump > pump pomp poop plop ploy play We don\'t have enough free time these days to do this by hand, but we can automate the procedure. You will create a graph of a large number of words with edges between words that differ by only a single letter. In fact, since it should be clear that each word in the above list transformation has the same number of letters, you will be creating a number disjoint graphs, one for words with three letters, one for words with four letters and so forth. Armed with this graph, you will perform a breadth-first search of the graph starting from a given starting word. As usual, as you perform the search, you will mark the parent of each visited node. Also, you will backhwards to the given starting word. This will be the shortest path from the starting word to the ending word A suitable list of words is the dictionary built in to any Linux system. I have placed one on the \"N\' drive on our folder. It is called simply amer roughly 100,000 words. rican_english. You should use this for your project; it contains r case, and some also contain apostrophes. You should transform all the words to upper or lower case-it doesn\'t matter t which--and discard those that contain apostrophes. When building your graph you should use the adjacency list representation. You will find it convenient to accumulate a map from each word entered into the graph to its index in the adjacency list. You may find it convenient to use the following structures when building your graph:

Solution

program

   #include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution
{
bool is_changeable(const string& lhs, const string& rhs)
{
size_t count = 0;
for(auto l = lhs.cbegin(), r = rhs.cbegin(); l != lhs.cend(); ++l,++r)
if(*l != *r) ++count;
return count == 1; }
public:
using Level = vector<string>;
int ladderLength(string start, string end, unordered_set<string> &dict)
{
if(dict.empty())
return 0;
auto d = dict;
d.erase(start);
d.erase(end);
if(d.empty())   
return 2;
auto next_level = [&](const Level& curr) -> Level
{
Level ret;
for(const auto& s : curr)
for(const auto& attempt : d)
if(is_changeable(s,attempt)) ret.push_back(attempt);
return ret;
};
auto if_found = [&](const Level& lvl) -> bool
{
for(const auto& s : lvl)
if(is_changeable(s,end)) return true;
return false;
};
size_t count = 0;
for(auto curr = Level{start}; !if_found(curr); curr = next_level(curr))
{
if(curr.empty()) return 0;
for(const auto& s : curr) d.erase(s);
++count;
}
return count + 2;
}
}