sudo-code implementation of the algorithm is enough Image text transcribed for a

Question

sudo-code implementation of the algorithm is enough

Image text transcribed for accessibility: Suppose you are given three strings of characters: X, Y. and Z. where | X | = n, |Y| = m, and |Z| = n + m. Z is said to be a shuffle of X and Y iff Z can be formed by interleaving the characters from X and Y in a way that maintains the left-to-right ordering of the characters from each string. Show that cchocohilaptes is a shuffle of chocolate and chips, but chocochilatspe is not. Give an efficient dynamic-programming algorithm that determines whether Z is a shuffle of X and Y. Hint: the values of the dynamic programming matrix you construct should be Boolean, not numeric.

Explanation / Answer

PART 1
showing CCHOCOHILAPTES is a shuffle of CHOCOLATE AND CHIPS
index of CCHOCOHILAPTES index of CHOCOLATE index of CHIPS
i=0           j=0 k=0
Z[i]=X[] i=1 j=1 k=0
Z[i]=Y[k] i=2       j=1 k=1
Z[i]=X[j] i=3 j=2 k=1
Z[i]=X[j] i=4 j=3 k=1
Z[i]=X[j] i=5 j=4 k=1
Z[i]=Y[k] i=6 j=4 k=2
Z[i]=Y[k] i=7 j=4 k=3
Z[i]=X[j] i=8 j=5 k=3
Z[i]=X[j] i=9 j=6 k=3
Z[i]=Y[k] i=10 j=6 k=4
Z[i]=X[j] i=11 j=7 k=4
Z[i]=X[j] i=12 j=8 k=4
Z[i]=Y[j] i=13 j=8 k=5

since end of all string are reached..this shows that CCHOCOHILAPTES is a shuffle of CHOCOLATE AND CHIPS

showing CHOCOCHILATSPE is NOT shuffle of CHOCOLATE AND CHIPS
index of CHOCOCHILATSPE index of CHOCOLATE index of CHIPS
i=0           j=0 k=0
Z[i]=X[j] i=1 j=1 k=0
Z[i]=X[j] i=2       j=2 k=0
Z[i]=X[j] i=3 j=3 k=0
Z[i]=X[j] i=4 j=4 k=0
Z[i]=X[j] i=5 j=5 k=0
Z[i]=Y[k] i=6 j=5 k=1
Z[i]=Y[k] i=7 j=5 k=2
Z[i]=Y[k] i=8 j=5 k=3
Z[i]=X[j] i=9 j=6 k=3
Z[i]=X[j] i=10 j=7 k=3
Z[i]=X[j] i=11 j=8 k=3
Z[i]!=X[j] OR Z[i]!=Y[k] j=8 k=3

since end of all string are not reached..this shows that CHOCOCHILATSPE is not a shuffle of CHOCOLATE AND CHIPS

part 2

#include <iostream>
#include <string.h>
using namespace std;

// function that returns true if C is
// an interleaving of A and B, otherwise false.
bool isInterleaved(char* A, char* B, char* C)
{
int M = strlen(A), N = strlen(B);

// Let us create a 2D table to store solutions of
// subproblems. C[i][j] will be true if C[0..i+j-1]
// is an interleaving of A[0..i-1] and B[0..j-1].
bool IL[M+1][N+1];
memset(IL, 0, sizeof(IL)); // Initialize all values as false.

// C can be an interleaving of A and B only of sum
// of lengths of A & B is equal to length of C.
if ((M+N) != strlen(C))
return false;

// Process all characters of A and B
for (int i=0; i<=M; ++i)
{
for (int j=0; j<=N; ++j)
{
// two empty strings have an empty string
// as interleaving
if (i==0 && j==0)
IL[i][j] = true;

// A is empty
else if (i==0 && B[j-1]==C[j-1])
IL[i][j] = IL[i][j-1];

// B is empty
else if (j==0 && A[i-1]==C[i-1])
IL[i][j] = IL[i-1][j];

// Current character of C matches with current character of A,
// but doesn't match with current character of B
else if(A[i-1]==C[i+j-1] && B[j-1]!=C[i+j-1])
IL[i][j] = IL[i-1][j];

// Current character of C matches with current character of B,
// but doesn't match with current character of A
else if (A[i-1]!=C[i+j-1] && B[j-1]==C[i+j-1])
IL[i][j] = IL[i][j-1];

// Current character of C matches with that of both A and B
else if (A[i-1]==C[i+j-1] && B[j-1]==C[i+j-1])
IL[i][j]=(IL[i-1][j] || IL[i][j-1]) ;
}
}

return IL[M][N];
}
int main()
{
cout<<"enter string X , Y , and Z"<<endl;
char a[20],b[20],c[20];
   cin>>a>>b>>c;
   if(isInterleaved(a,b,c))
   cout<<c<<" is interleaved of "<<a<<" and "<<b<<endl;
   else
   cout<<c<<" is not interleaved of "<<a<<" and "<<b<<endl;
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.