Hey I have trouble doing my final project, which is a word ladder, in c++. I hav
ID: 3761879 • Letter: H
Question
Hey I have trouble doing my final project, which is a word ladder, in c++. I have figured out how to change the word, the problem is how to find the shortest Word Ladder, I searched that I need to use Breadth-first search but I don't understand the algorithem. Are there any other way to find the shortest word ladder? My code is shown below, please feel free to help me improve it. Thanks!
#include<iostream>
#include<string>
using namespace std;
class wordLadder
{
public:
string startWord;
string finalWord;
int choice;
char letter;
int step = 0;
void inPut()
{
cout<<"input start word with 4 letters: "<<endl;
cin>>startWord;
cout<<"input final word with 4 letters"<<endl;
cin>>finalWord;
}
void changeWord()
{
do
{
cout<<"input the # of letter you want to change: "<<endl;
cin>>choice;
cout<<"enter the letter "<<endl;
cin>>letter;
startWord[choice-1] = letter;
cout<<startWord[0]<<startWord[1]<<startWord[2]<<startWord[3]<<endl;
if(startWord!=finalWord)
{
cout<<"not yet, try again"<<endl;
cout<<"------------------"<<endl;
}
step++;
}
while(startWord!=finalWord);
if(startWord == finalWord)
{
cout<<"you win"<<endl;
cout<<"step used: "<<step<<endl;
}
}
};
int main()
{
wordLadder Play;
Play.inPut();
Play.changeWord();
return 0;
}
Explanation / Answer
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that only one letter can be changed at a time and each intermediate word must exist in the dictionary.
For example, given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
One shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", the program should return its length 5.
void processMainGame(Lexicon dictionary, string startWord, string endWord)
{
Queue<Vector<string> > theFIFO;
Lexicon alreadyUsed;
string nextStr;
theFIFO.clear();
Vector<string> addToQueue;
addToQueue.add(startWord);
theFIFO.enqueue(addToQueue);
while (true)
{
if (theFIFO.size() ==0)
{
cout << "Nope nothing found! no ladder"<< endl;
break;
}
Vector<string> newString = theFIFO.dequeue();
while (true)
{
nextStr = findNextWord(newString[newString.size()-1], dictionary, alreadyUsed);
if (nextStr == endWord)
{
cout << "FOUND ladder !!" << endl;
foreach (string list in newString)
{
cout << list << " - ";
}
cout << endWord << endl << endl;
return;
} else if (nextStr != "")
{
Vector<string> addMore = newString;
addMore.add(nextStr);
theFIFO.enqueue(addMore);
}
else if (nextStr =="")
break;
alreadyUsed.add(nextStr);
}
}
}