In: Computer Science
Need this in C++:
Suppose that you are given a set of words; and two words from the set: word 1 and word 2.
Write a program which will transform word 1 into word 2 by changing a single letter in word 1 at a time.
Every transition that word 1 takes will have to be in the set of words.
You must output the smallest sequence of transitions possible to convert word 1 into word 2.
You may assume that all the words in the dictionary are the same length.
The first line will be word 1 and word 2 separated by a comma, followed by the set of words. The set of words will be terminated by a ‘-1’.
Input:
DOG,GOD
DOG
BOG
GOG
ABH
GOD
THU
IOP
-1
Output:
DOG -> GOG -> GOD
Input:
HOUSE,JOUKS
MOUSE
HIUKE
HIUKS
HOUSH
LOUSE
HOZKS
SOUSE
HOUKS
HOUSE
HOUKE
JOUKZ
JOUKS
HOIKE
-1
Output:
HOUSE -> HOUKE -> HOUKS -> JOUKS
#include<bits/stdc++.h>
using namespace std;
bool isadjacent(string& a, string& b)
{
int count = 0;
int n = a.length();
for (int i = 0; i < n; i++)
{
if (a[i] != b[i]) count++;
if (count > 1) return
false;
}
return count == 1 ? true : false;
}
struct QItem
{
string word;
int len;
};
void shortestChainLen(string& start, string& target,
set<string> &D)
{
queue<QItem> Q;
QItem item = {start, 1};
Q.push(item);
while (!Q.empty())
{
QItem curr = Q.front();
Q.pop();
string temp;
for (set<string>::iterator it
= D.begin(); it != D.end(); it++)
{
temp =
*it;
if
(isadjacent(curr.word, temp))
{
item.word = temp;
item.len=curr.len+1;
Q.push(item);
cout<<temp<<"->";
D.erase(temp);
}
if (temp == target)
return ;
}
}
return ;
}
int main()
{
string start;
string target;
string s;
char found;
set<string> D;
cin>>s;
for(int i=0; i<s.length();i++)
if (s[i]==',')
found =i;
start= s.substr(0,found);
target= s.substr(found+1,s.length()-1);
cin>>s;
while(s!="-1")
{
D.insert(s);
cin>>s;
};
cout<<start<<"->"
shortestChainLen(start, target, D);
cout<<target;
return 0;
}