Interview Question
Country: United States
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");
}
u see your code only does a trivial check it will fail for many test cases
for eg:- let's say A="AAA" and B="AAB" and interlevead string be C="AABAAA"
so your statement
if (*ptrA++ != *ptrC++) {
break;
}
will give true for first 2 A's but after that your logic will fail as C will now point to "B" A is pointing to 'A' and B is also pointing to "A"..And you will come out of the loop.
because of these test cases you need to come with a dynamic programming.
Which is there in my post below you.
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;
}
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()];
}
Construct a (n1+1)*(n2+1) table, A[0 .. n1][0 .. n2], where n1 and n2 is the length of s1 and s2, respectively.
- blackfever January 23, 2014A[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]