CODEWITHSUNDEEP
algorithm
Umar Ghulam
Umar Ghulam

Reputation: 53

Given string x,y and z. Determine if z is a shuffle

I am trying this problem:

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 if and only if 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.

Give an efficient 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

What I don't understand is why everyone is presenting a dynamic programming recursive solution.

Can't we just do the following n+m algo:

  1. Maintain two pointers i and j, i points to chars in string x and j for string y.

  2. Iterate (with iterator k) through z, for every char z[k] if it match x[i] increment i, if it match y[j] increment j

    2.1. if k > i+j then return false

    2.2. if k == z.length() and i or j != x.length(), y.length() respectively then return false

  3. return true

edited according to Tanmay Patil 's post

Upvotes: 2

Views: 855

Answers (2)

Tanmay Patil
Tanmay Patil

Reputation: 7057

Well, the problem statement clearly says

Give an efficient dynamic ­programming algorithm

So that should explain

everyone is presenting a dynamic programming recursive solution

Even then, it can be solved in an iterative way as you mentioned. And it is not a n^2 algorithm, it's time complexity is n+m

Good luck.

Upvotes: 3

user1985657
user1985657

Reputation:

You're right.

You never, ever HAVE TO use recursive algorithms. You're free to do so, but you can ALWAYS use an interative routine.

In this example, you could use arrays or allocate a memory block large enough to hold the result.

Upvotes: 0

Related Questions