Question

In: Computer Science

Need this in C++: Suppose that you are given a set of words; and two words...

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

Solutions

Expert Solution


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


Related Solutions

Suppose that you are given a set of words; and two words from the set: word...
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...
Suppose we are given two skip lists, one storing a set A of m keys, and...
Suppose we are given two skip lists, one storing a set A of m keys, and the other storing a set B of n keys. Describe and analyze an algorithm to merge these into a single skip list storing the set A ∪ B in O(n + m) expected time. Do not assume that every key in A is smaller than every key in B; the two sets could be arbitrarily intermixed.
You work for an insurance company and you need to set price on a two-year warranty...
You work for an insurance company and you need to set price on a two-year warranty policy. The item of interest is a Dutch oven. Your boss wants the policy to generate $9 of profit. You do some research and find that with probability 0.1 the lid will need to be replaced and that will cost the company $80, and with probability 0.05 the pot will need to be replaced and that will cost the company $150. What should the...
C++ language. Suppose you are given a list of students registered in a course and you...
C++ language. Suppose you are given a list of students registered in a course and you are required to implement an Linked List of student. Each student in the list has name, regNo and cGpa. You task is to implement following function related to Linked List. insertStudent() : This function, when called will prompt user to enter his/her choice of insertion. The options are 1. Insert student at the start of linked list 2. Insert student at the end of...
I need the Java Code and Flowchart for the following program: Suppose you are given a...
I need the Java Code and Flowchart for the following program: Suppose you are given a 6-by-6 matrix filled with 0s and 1s. All rows and all columns have an even number of 1s. Let the user flip one cell (i.e., flip from 1 to 0 or from 0 to 1) and write a program to find which cell was flipped. Your program should prompt the user to enter a 6-by-6 array with 0s and 1s and find the first...
C++ Funcion For this lab you need to write a program that will read in two...
C++ Funcion For this lab you need to write a program that will read in two values from a user and output the greatest common divisor (using Euclidean algorithm) to a file. You will also need to demonstrate using ostream and ostringstream by creating 2 functions to output your print heading: one that uses ostream and the other uses ostringstream. Using ostream and ostringstream Write two PrintHeader functions that will allow you to output to the screen and to an...
Suppose that you are given the following information about a particular economy C = 500 +...
Suppose that you are given the following information about a particular economy C = 500 + 0.75(Y –T) Where C = consumption T = 1,000 T = taxes I = 750 – 25r I = investment G = 1,000 G = government spending M = 3,200 M = Money Supply P = 2 P = Price level (M/P)d = M/P = 0.5Y – 50r r = real interest rate in percent (i.e., 10 = 10%) a)Using this information generate the...
Suppose you are given an integer c and an array, A, indexed from 1 to n,...
Suppose you are given an integer c and an array, A, indexed from 1 to n, of n integers in the range from 0 to 5n (possibly with duplicates). i.e. 0 <= A[i ] <= 5n " I = {1, .., n}. a.) Write an efficient algorithm that runs in O(n) time in a pseudo code for determining if there are two integers, A[i] and A[j], in A whose sum is c, i.e. c = A[i] + A[j], for 1...
For the following two questions you need to provide a code in C 1. Build a...
For the following two questions you need to provide a code in C 1. Build a double linked list with 5 in the first node following the instructions: Insert a node with 3 at the top of the list Insert a node with 10 at the bottom of the list Insert a node with 7 between nodes with 5 and 10 2. Start deleting nodes from the list in the following order; Delete the node with 7 Delete the node...
Suppose A is the set of positive real numbers, and suppose u and v are two...
Suppose A is the set of positive real numbers, and suppose u and v are two strictly increasing functions.1 It is intuitive that u and v are ordinally equivalent, since both rank larger numbers higher, and therefore generate the same ranking of numbers. Write this intuition as a proof.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT