hari6988's blog

Shuffle problem for 2 strings
By hari6988, 14 years ago, In English
Hi,

I am new to Dynamic programming and i came across this problem. I couldn't come up with a proper state for this problem. Can you please help me ?? The problem is as follows:

Suppose you are given three strings of English letters X = x1x2…xm, Y = y1y2…ym, Z = z1z2…zm+n. The string Z is a shuffle of X and Y if and only if Z can be formed by interspersing the characters from X and Y in a way that preserves the left-to-right ordering of the characters from X and Y respectively. For example, cchocohilaptes is a shuffle of chocolate and chips, but chcccochilatspe is not.

Find a DP algorithm to determine whether Z is a shuffle of X and Y .

  • Vote: I like it
  • +1
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I think you'd better to struggle through this problem by your own if you want to master DP. It is just the problem for start learning.

Regard Longest common subsequence and then turn back to your problem. You need to have matrix of length(X)*length(Y) and in each cell (a,b) just write the number (c) of character in Z which could be reached by adding X(a) or Y(b) to the beginning of Z already constructed.

May be I am slightly wrong, but idea is just this.
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

DP is a bruteforce, for which we can remember their states in such a way, that it works faster. Let's construct all posssible strings S which is a shuffle of x and y. It can be done recursively. rec(s = "", x, y); at each step we can add to s first character of string x, and then remove this character from beginning of x, or we can add first character of string y, and remove it from y. At the last step x and y will be empty, and the length of s will be n+m. At last step we can compare s and z, if these strings are equal answer is TRUE.

now we will make DP from this bruteforce algorithm.

Note1: We can compare strings s and z not only at the last step, but after adding each consecutive character. If, at some step, we cannot add to s a character, so that corresponding character of z is the same, asnwer in this branch of recusion always will be FALSE.

Note2: The state of recursion can be determined by remaining lengths of x and y. Length of s will be equal n + m - x.length() - y.length(), and s will be a prefix of z.

→ Reply