Using Dynamic Programming:· Try to find an efficient solution to this problem: Z

Question

Using Dynamic Programming:·

Try to find an efficient solution to this problem: Zippers: Given three strings, you are to determine whether the third string can be formed by combining the characters in the first two strings. The first two strings can be mixed arbitrarily, but the characters from each must stay in their original order in the third string. For example, consider forming "tcarete" from "cat" and "tree"

: String A: c a t

String B: t r e e

String C: t c a r e t e

As you can see, we can form string C by selecting the first charcter of "tree", followed by the first 2 characters of "cat", followed by the second and third characters of "tree", followed by the last charcter of "cat" and "tree" respectively.

As a second example, consider forming "catrtee" from "cat" and "tree":

String A: c a t

String B: t r e e

String C: c a t r t e e

The answer for this input is also 'yes' Finally, notice that it is impossible to form "cttaree" from "cat" and "tree", meaning the answer for this input would be 'no'. Zipper Problem Input · String A = a1, a2, a3, ... , an · String B = b1, b2, b3, ..., bm · String C = c1, c2, c3, ..., cm+n Output: Output yes if A and B can be combined (zippered) into string C. Output no if A and B cannot be combined to form C. As always: · Prove that your algorithm is correct. · Analyze the run time of your algorithm.

Explanation / Answer

IsInterleaved

Let IL[i][j] is true if C[0...i+j-1] is interleaving of A[0...i-1] and B[0....j-1]

Initialise IL[i][j] to false for all i, j

IL[0][0] = true

If A is empty just check if B has same charcters in order

If B is empty ust check if A has same characters in order

Now either of these three cases can happen

For each char of A

for each char of B

                IL[i][j] = IL[i][j-1];

IL[i][j]=(IL[i-1][j] || IL[i][j-1]) ;

With this IL[M][N] will be true if it is interleaving else false, where M is lengh of A and N is length of B

Time Complexity: O(MN) as it is going over length of B for each char of A

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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