Check if a string is a shuffle of two other given strings

Question

This is a question from The Algorithm Design Manual: 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 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 This is what I tried: Initially, I made a 1-D char array and pointers to the starting characters of X,Y,Z respectively. If Z-pointer with matches X-pointer store X in the char array else check the same with Y-pointer.If each entry in the char array is not different from its last entry, Z is not interleaved. Can someone help me with this problem?

Accepted Answer

Following approach should give you an idea.

Define the condition `d(s1,s2,s3) = (s1 + s2 == s3) { s3 is a shuffle of s1 and s2 }`

We have to find `d( X, Y, Z )`.

if lengths of s1 and s2 are 1 each and length of s3 = 2,

```
d( s1,s2,s3 ) = { (s1[0] == s3[0] && s2[0] == s3[1]) || (s1[0] == s3[1] && s2[0] == s3[0])
```

Similarly d can be obtained for empty strings.

For strings of arbitrary length, following relation holds.

```
d( s1,s2,s3 ) = { ( d( s1-s1[last],s2,s3 - s3[last]) && s1[last] == s3[last] )
                  || ( d( s1,s2 - s2[last],s3 - s3[last]) && s2[last] == s3[last] )
                }
```

You can compute the `d()` entries starting from zero length strings and keep checking.

Check if a string is a shuffle of two other given strings

Solution

Problem