can anyone help me, basically its the word ladder problem, i found the length of
ID: 656851 • Letter: C
Question
can anyone help me, basically its the word ladder problem, i found the length of word from code to data is five, but i just need to print out the words leading to data, can anyone help me ?
#include <iostream>
#include <string>
#include <vector>
#include <unordered_set> //hash values to allow for faster access to individual elements directly
#include <queue>
#include <map> //constructs a map container object, intializing its contents depending on the constructor
#include <fstream>
#include <stack>
using namespace std;
class Node
{
string str;
int lvl;
public:
Node() // default constructor
{
str = "";
lvl = 0;
}
Node(string s, int le)
{
str = s;
lvl = le;
}
int getlvl() //Get functions
{
return lvl;
}
string getString()
{
return str;
}
};
vector<string>final_path;
vector<string> createWordList(string , unordered_set<string> &); //forward declarations
int wordLadder(string, string, unordered_set<string> &);
int main()
{
string Word1, Word2, w;
unordered_set<string> dictionary;
ifstream inFile("hw2_dictionary.txt");
cout << "The Dictionary is being created...";
while (!inFile.eof())
{
getline(inFile, w);
dictionary.insert(w);
}
system("CLS");
cout << "Please enter 2 words: " << endl;
cout << "First Word: ";
getline(cin, Word1);
cout << "Second Word: ";
getline(cin, Word2);
system("CLS");
cout <<"Searching for the ladder...";
int answer = wordLadder(Word1, Word2, dictionary);
system("CLS");
if (answer == 0)
cout << "No path found.";
else
cout << "There is " << answer <<" words from " << Word1 << " to " << Word2 << endl;
return 0;
}
vector<string> createWordList(string str, unordered_set<string> &dictionary) //search the dictionary
{
vector<string> words;
string s = str;
for (int i = 0; i < str.size(); i++)
{
s = str;
for (char j = 'a'; j <= 'z'; j++) //Changing one letter at a time
{
s[i] = j;
if (dictionary.find(s) != dictionary.end())
words.push_back(s);
}
}
return words;
}
int wordLadder(string start, string end, unordered_set<string> &dictionary) //Get ladder length of words
{
stack<string> path;
queue<Node> FowardQ, ReverseQ; // Bidirectional search
map<string, bool> HashF, HashB; // 2 hashes with the possible words as keys and a boolean flag
for (auto i = dictionary.begin(); i != dictionary.end(); i++)
{
HashF[*i] = false; //setting the flag as false
HashB[*i] = false;
}
int forLevel = 1; //setting the beginning position for both hash
int revlevel = 1;
FowardQ.push(Node(start, 1)); //using a stack to push first word on to the que
ReverseQ.push(Node(end , 1)); // pushes the second word on to the que
while (!FowardQ.empty() && !ReverseQ.empty())
{
if (FowardQ.size() < ReverseQ.size()) //checks if the que is empty and size
{
while (!FowardQ.empty() && FowardQ.front().getlvl() == forLevel)
{
vector<string> startList = createWordList(FowardQ.front().getString(), dictionary);//create list of words
for (auto i = startList.begin(); i != startList.end(); i++)
{
if (!HashF[*i])
{
HashF[*i] = true; //common word and path found.
if (HashB[*i])
return FowardQ.front().getlvl() + ReverseQ.back().getlvl();//return their positions
FowardQ.push(Node(*i, forLevel + 1));
}
}
FowardQ.pop();
}
forLevel++; //how deep in the path finding we its in
}
else
{
while (!ReverseQ.empty() && ReverseQ.front().getlvl() == revlevel)
{
vector<string> endList = createWordList(ReverseQ.front().getString(), dictionary); //crate Word List
for (auto i = endList.begin(); i != endList.end(); i++)
{
if (!HashB[*i])
{
HashB[*i] = true; //path found
if (HashF[*i])
return ReverseQ.front().getlvl() + FowardQ.back().getlvl();
ReverseQ.push(Node(*i, revlevel + 1));
}
}
ReverseQ.pop();
}
revlevel++; //depth of path
}
}
return 0; // no path found
}
Explanation / Answer
// I modified the code you given. now check it with the dictionary file hw2_dictionary.txt you already have.
#include <iostream>
#include <string>
#include <vector>
#include <unordered_set> //hash values to allow for faster access to individual elements directly
#include <queue>
#include <map> //constructs a map container object, intializing its contents depending on the constructor
#include <fstream>
#include <stack>
using namespace std;
class Node
{
string str;
int lvl;
public:
Node() // default constructor
{
str = "";
lvl = 0;
}
Node(string s, int le)
{
str = s;
lvl = le;
}
int getlvl() //Get functions
{
return lvl;
}
string getString()
{
return str;
}
};
vector<string>final_path;
vector<string> createWordList(string , unordered_set<string> &); //forward declarations
int wordLadder(string, string, unordered_set<string> &);
int main()
{
string Word1, Word2, w;
unordered_set<string> dictionary;
stack<string> path;
ifstream inFile("hw2_dictionary.txt");
cout << "The Dictionary is being created...";
while (!inFile.eof())
{
getline(inFile, w);
dictionary.insert(w);
}
system("CLS");
cout << "Please enter 2 words: " << endl;
cout << "First Word: ";
getline(cin, Word1);
cout << "Second Word: ";
getline(cin, Word2);
system("CLS");
cout <<"Searching for the ladder...";
int answer = wordLadder(Word1, Word2, dictionary,path);
system("CLS");
if (answer == 0)
cout << "No path found.";
else
cout << "There is " << answer <<" words from " << Word1 << " to " << Word2 << endl;
return 0;
}
vector<string> createWordList(string str, unordered_set<string> &dictionary) //search the dictionary
{
vector<string> words;
string s = str;
for (int i = 0; i < str.size(); i++)
{
s = str;
for (char j = 'a'; j <= 'z'; j++) //Changing one letter at a time
{
s[i] = j;
if (dictionary.find(s) != dictionary.end())
words.push_back(s);
}
}
return words;
}
int wordLadder(string start, string end, unordered_set<string> &dictionary,stack<string> &path) //Get ladder length of words
{
// stack<string> path;
queue<Node> FowardQ, ReverseQ; // Bidirectional search
map<string, bool> HashF, HashB; // 2 hashes with the possible words as keys and a boolean flag
for (auto i = dictionary.begin(); i != dictionary.end(); i++)
{
HashF[*i] = false; //setting the flag as false
HashB[*i] = false;
}
int forLevel = 1; //setting the beginning position for both hash
int revlevel = 1;
FowardQ.push(Node(start, 1)); //using a stack to push first word on to the que
ReverseQ.push(Node(end , 1)); // pushes the second word on to the que
while (!FowardQ.empty() && !ReverseQ.empty())
{
if (FowardQ.size() < ReverseQ.size()) //checks if the que is empty and size
{
while (!FowardQ.empty() && FowardQ.front().getlvl() == forLevel)
{
vector<string> startList = createWordList(FowardQ.front().getString(), dictionary);//create list of words
for (auto i = startList.begin(); i != startList.end(); i++)
{
if (!HashF[*i])
{
HashF[*i] = true; //common word and path found.
if (HashB[*i])
return FowardQ.front().getlvl() + ReverseQ.back().getlvl();//return their positions
FowardQ.push(Node(*i, forLevel + 1));
}
}
path=FowardQ.pop();
}
forLevel++; //how deep in the path finding we its in
}
else
{
while (!ReverseQ.empty() && ReverseQ.front().getlvl() == revlevel)
{
vector<string> endList = createWordList(ReverseQ.front().getString(), dictionary); //create Word List
for (auto i = endList.begin(); i != endList.end(); i++)
{
if (!HashB[*i])
{
HashB[*i] = true; //path found
if (HashF[*i])
return ReverseQ.front().getlvl() + FowardQ.back().getlvl();
ReverseQ.push(Node(*i, revlevel + 1));
}
}
path=ReverseQ.pop();
}
revlevel++; //depth of path
}
}
return 0; // no path found
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.