CareerCup

Construct a (n1+1)*(n2+1) table, A[0 .. n1][0 .. n2], where n1 and n2 is the length of s1 and s2, respectively.
A[i][j] = true, i.e. s3[0 .. i+j-1] is an interleaving of s1[0 .. i-1] and s2[0 .. j-1].
Thus, A[n1][n2] represents whether s3 is a interleaving of s1 and s2.
To build up such a table,
1.Set A[0][0] = true. Period.
2.Initialize the first row. The first row means whether s1[0 .. (n1-1)] matches s3[0 .. (n1-1)], correspondingly.
3.Similarly, initialize the first column which means whether s2[0 .. (n2-1)] matches s3[0 .. (n2-1)], correspondingly.
Now we fill up the table. For A[i][j], s3[0 .. (i+j-1)] match? s1[0 .. i-1] weaving s2[0 .. j-1]
4.Note that A[i-1][j] comes from s1[0 .. i-2] weaving s2[0 .. j-1]. Thus, if it is true, we need to compare s1[i-1] with s3[i+j-1].
Similarly, A[i][j-1] comes from s1[0 .. i-1] weaving s2[0 .. j-2]. Thus, if it is true, compare s2[j-1] with s3[i+j-1].

5.Return A[n1][n2]

If I have to do this exercise once, I would just do a linear walk through the characters and find the answer like below.

Assume sizea, sizeb sizec are the respective array sizes.

        // NOTE: watch out for the \0 at the end.
	if ((sizea != sizeb) || ((sizec-1) != (sizea-1+sizeb-1))) {	// -1 => take out \0 at the end.
		printf("Perfect interleaving not possible.\n");
		return -1;
	}

	ptrA = a; 	ptrB = b; 	ptrC = c;
	sizea -= 1;	// cut off the \0 char

	while (sizea) {
		if (*ptrA++ != *ptrC++) {
			break;
		}

		if (*ptrB++ != *ptrC++) {
			break;
		}

		sizea--;
	}

	if (sizea == 0) {
		printf("Perfect interleave.\n");
	} else {
		printf("No interleave.\n");
	}

public static boolean isInterleavingString(String s1, String s2, String s3) {
		int p1 = 0;
		int p2 = 0;
		int prevStr = 0;
		for (int i = 0; i < s3.length(); i++) {

			if (prevStr == 0) {
				if (p1 < s1.length() && s3.charAt(i) == s1.charAt(p1)) {
					p1++;
				} else if (p2 < s2.length() && s3.charAt(i) == s2.charAt(p2)) {
					p2++;
					prevStr = 1;
				} else {
					return false;
				}
			} else {
				if (p2 < s2.length() && s3.charAt(i) == s2.charAt(p2)) {
					p2++;
				} else if (p1 < s1.length() && s3.charAt(i) == s1.charAt(p1)) {
					p1++;
					prevStr = 0;
				} else {
					return false;
				}
			}
		}
		return p1 == s1.length() && p2 == s2.length();
	}

Test Cases:
isInterleavingString("aabcc", "dbbca", "aadbbcbcac") Result: true
isInterleavingString("aabcc", "dbbca", "aadbbbaccc") Result: false

can handle duplicates, with DP

public boolean isInterleave(String s1, String s2, String s3) {
        if (s3.length() != s1.length() + s2.length()) return false;
        int[][] dp = new int[s1.length()+1][s2.length()+1];
        return isInterleave(s1,s2,0,0,s3,dp);
    }
    
    private boolean isInterleave(String s1, String s2, int i1, int i2, String s3, int[][] dp) {
        if (i1 == s1.length() && i2 == s2.length()) return true;
        if (dp[i1][i2] > 0) return dp[i1][i2] == 2;
        boolean result = false;
        if (i1 == s1.length()) result = s2.charAt(i2) == s3.charAt(i1+i2) && isInterleave(s1,s2,i1,i2+1,s3,dp);
        else if (i2 == s2.length()) result = s1.charAt(i1) == s3.charAt(i1+i2) && isInterleave(s1,s2,i1+1,i2,s3,dp);
        else if (s1.charAt(i1) == s3.charAt(i1+i2) && isInterleave(s1,s2,i1+1,i2,s3,dp)) result = true;
        else if (s2.charAt(i2) == s3.charAt(i1+i2) && isInterleave(s1,s2,i1,i2+1,s3,dp)) result = true;
        dp[i1][i2] = result ? 2 : 1;
        return result;
    }

How about:

bool match(const char* s1, const char* s2, const char* s3)
{
    if (*s3 == '\0')
        return *s1 == '\0' && *s2 == '\0';

    return (*s1 == *s3) && match(s1 + 1, s2, s3 + 1) ||
           (*s2 == *s3) && match(s1, s2 + 1, s3 + 1);
}

Java DP solution

public boolean isInterleave(String s1, String s2, String s3) {
	if ( (s1.length()+s2.length()) != s3.length() ) return false;
	boolean[][] DP= new boolean[s1.length()+1][s2.length()+1];
	//base case: an empty string is always the interleave of two other empty string 
	for (int p1 = 0; p1 <= s1.length(); p1++) {
		for (int p2 = 0; p2 <= s2.length(); p2++) {
			DP[p1][p2] = ( p1==0 && p2==0 ) //Base case of 2 empty strings
					|| ( p1 > 0 && DP[p1-1][p2] && s1.charAt(p1-1)==s3.charAt(p1+p2-1) )
					|| ( p2 > 0 && DP[p1][p2-1] && s2.charAt(p2-1)==s3.charAt(p1+p2-1) );
		}
	}
	return DP[s1.length()][s2.length()];
}

Can s3 contain common characters for s1 and s2? E.g s1=abc, s2, =abc, s3 = abcd
What is the correct output true or false?