Find if a string is formed by interleaving two strings
Problem: Given a string 's' and two candidate strings 's1' and 's2', find if 's' is formed by interleaving of 's1' and 's2'.
Interleaving is defined as formed by picking characters randomly from s1 and s2 but preserving the order of characters in s1 and s2.
Example: If s1 = 'ABC' and s2 = 'def', then 'AdBeCf' is an interleaved string.
'ABCdef' is also an interleaved string and so is 'ABdeCf'.
'AdefCB' is not an interleaved string because the order of 'BC' is not maintained.
Solution:
A recursive solution for this is as follows:
Clearly, this can be optimized by dynamic programming because its calculating subproblems over and over again.
Dynamic Programming Solution
boolean isInterleaved(String A, String B, String C)
{
int M = A.length();
int N = B.length();
if ((M+N) != C.length())
return false;
// lookup[i][j] is true if C[0..i+j-1] is an interleaving of A[0..i-1] and B[0..j-1].
boolean lookup[][] = new boolean[M+1][N+1];
for (int i=0; i<=M; i++)
{
for (int j=0; j<=N; j++)
{
// If both A and B are empty, then C must also be empty (due to length matching)
// And since one empty string is interleaving of other two empty
// strings, lookup[0][0] is true.
if (i==0 && j==0)
lookup[i][j] = true;
// If A is empty, check one-to-one match with B
else if (i==0 && B[j-1]==C[j-1])
lookup[i][j] = lookup[i][j-1];
// If B is empty, check one-to-one match with A
else if (j==0 && A[i-1]==C[i-1])
lookup[i][j] = lookup[i-1][j];
// Regular check for interleaving
if (A[i-1]==C[i+j-1] && B[j-1]==C[i+j-1])
lookup[i][j]=(lookup[i-1][j] || lookup[i][j-1]);
else if(A[i-1]==C[i+j-1])
lookup[i][j] = lookup[i-1][j];
else if (B[j-1]==C[i+j-1])
lookup[i][j] = lookup[i][j-1];
// Its too soon to return a false if C[i+j-1] matches neither A or B.
// Think why?
}
}
return lookup[M][N];
}
Explanation for lines 43 and 44
Check the loops in the dynamic programming solution.
The first loop compares a part of first string with the complete second string.
If first loop is at an index 'k', it is possible that the interleaved string has a first string character on position 'k+1'
Since the loop is not allowing the first string to be completely visible (except in the last pass), it's not correct to terminate
if 'k+1'th character does not match.
Got a thought to share or found a bug in the code? We'd love to hear from you: