Question

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

Answer 1

#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;
}