Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,

Given:

s1 = "aabcc",

s2 = "dbbca",

When s3 = "aadbbcbcac", return true.

When s3 = "aadbbbaccc", return false.

// recurvise method, time limit exceeded for large dataset

public class Solution {

public boolean isInterleave(String s1, String s2, String s3) {

// Start typing your Java solution below

// DO NOT write main() function

if(s1.length() + s2.length() != s3.length())

return false;

if(s1.length()==0 || s2.length()==0 || s3.length()==0) {

if((s1 + s2).equals(s3))

return true;

else

return false;

}

if(s1.charAt(0)!=s3.charAt(0) && s2.charAt(0)!=s3.charAt(0))

return false;

if( s1.charAt(0)==s3.charAt(0) && isInterleave(s1.substring(1), s2, s3.substring(1)))

return true;

if( s2.charAt(0)==s3.charAt(0) && isInterleave(s1, s2.substring(1), s3.substring(1)))

return true;

return false;

}

}

//////////////////////////////////////////////////////////////////

// dynamic programming

public class Solution {

public boolean isInterleave(String s1, String s2, String s3) {

if(s3.length() != (s1.length() + s2.length()))

return false;

boolean [][] match = new boolean [s1.length()+1][s2.length()+1];

match[0][0]=true;

int i = 1;

while(i<=s1.length() && s1.charAt(i-1)==s3.charAt(i-1)) {

match[i][0]=true;

i++;

}

i = 1;

while(i<=s2.length() && s2.charAt(i-1)==s3.charAt(i-1)) {

match[0][i]=true;

i++;

}

for(i=1; i<=s1.length(); i++) {

for(int j=1; j<=s2.length(); j++) {

char c = s3.charAt(i+j-1);

if(c==s1.charAt(i-1))

match[i][j] = match[i-1][j] || match[i][j];

if(c==s2.charAt(j-1))

match[i][j] = match[i][j-1] || match[i][j];

}

}

return match[s1.length()][s2.length()];

}

}