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?

Solution 1

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.

Solution 2

First, let's start with some definitions. I write X[i] for the ith element of X and X[i) for the substring of X starting at index i.

For example, if X = abcde, then X[2] = c and X[2) = cde.

Similar definitions hold for Y and Z.

---

To solve the problem by dynamic programming, you should keep a 2D boolean array A of size (n+1) x (m+1). In this array, A[i, j] = true if and only if X[i) and Y[j) can be interleaved to form Z[i+j).

For an arbitrary (i, j), somewhere in the middle of the 2D array, the recurrence relation is very simple:

A[i, j] := X[i] = Z[i+j] and A[i+1, j]
        or Y[j] = Z[i+j] and A[i, j+1]

On the edges of the 2D array you have the case that either X or Y is already at its end, which means the suffix of the other should be equal to the suffix of Z:

A[m, j] := Y[j) = Z[m+j)
A[i, n] := X[i) = Z[i+n)
A[m, n] := true

---

If you first fill the border of the array (A[m, j] and A[i, n], for all i, j), you can then simply loop back towards A[0, 0] and set the entries appropriately. In the end A[0, 0] is your answer.

Solution 3

It is defined by following recurrence relation:-

S(i,j,k) = false

if(Z(i)==Y(k))
  S(i,j,k) = S(i,j,k)||S(i+1,j,k+1)

if(Z(i)==X(j))
  S(i,j,k) = S(i,j,k)||S(i+1,j+1,k)

Where S(i,j,k) corresponds to Z[i to end] formed by shuffle of X[j to end] and Y[K to end]

You should try to code this into DP on your own.

Solution 4

I think this is quite easy if you are solving this problem by using this approach with java

Java Based Solution

public class ValidShuffle {

    public static void main(String[] args) {
   
        String s1 = "XY";
        String s2 = "12";

        String results = "Y21XX";
    
        validShuffle(s1, s2, results);

    }

    private static void validShuffle(String s1, String s2, String result) {
        
        String s3 = s1 + s2;
        StringBuffer s = new StringBuffer(s3);

        boolean flag = false;

        char[] ch = result.toCharArray();

        if (s.length() != result.length()) {
            flag = false;
        } else {

            for (int i = 0; i < ch.length; i++) {
                
                String temp = Character.toString(ch[i]);

                if (s3.contains(temp)) {

                    s = s.deleteCharAt(s.indexOf(temp));
                    s3 = new String(s);
                    flag = true;
                    
                } else {
                    flag = false;
                    break;
                }

            }

        }

        if (flag) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }

    }

}

If any problem in my code then comment me please. thank you

View more solutions

Comments

[Abhishek Bansal]

Please show what you have tried.

[piyukr]

doesn't interleaving imply that successive characters in Z need to be from X and Y alternatively ?

[Abhishek Bansal]

No. Interleaving only implies that Z should contain all the characters in X and Y and in the same order as they were in the respective strings. For example, abc and def and be interleaved to form abcdef.