LeetCode: Interleaving String

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.

Solution

This is another perfect problem to practice Dynamic Programming.

My thoughts:

Firstly I oversimplified the problem. Thought it might work by iterate through s3 to match a letter either in S1 or S2. Of course it is wrong. Anti-example: s1= aa, s2=ab, s3=aaba.
Then I realized it can be solved with recursion. The implementation is as follows:

	public boolean isInterleave(String s1, String s2, String s3) {
	boolean ret1=false, ret2=false;
	// if(s1.length()==0&&s2.length()==0&&s3.length()==0 ) return true;
	if((s1.length()+s2.length()) != s3.length()) return false;
	if(s1.length()==0){
	if(s2.equals(s3))
	return true;
	else
	return false;
	}
	if(s2.length()==0){
	if(s1.equals(s3))
	return true;
	else
	return false;
	}
	if(s3.length()==0)
	{
	if(s1.length()==0 && s2.length()==0)
	return true;
	else
	return false;
	}
	/* int id1, id2, id3;
	for(id3=0, id2=0, id3=0; id3<s3.length(); id3++){
	char c = s3.charAt(id3);
	if(id1<s1.length() && c == s1.charAt(id1)){
	id1++;
	continue;
	}
	if(id2<s2.length() && c == s2.charAt(id2)){
	id2++;
	continue;
	}
	return false;
	}*/
	if(s3.charAt(0) == s1.charAt(0) && s1.length()>1 &&s3.length()>1)
	ret1 = isInterleave(s1.substring(1), s2, s3.substring(1));
	if(s3.charAt(0) == s2.charAt(0) && s2.length()>1 &&s3.length()>1)
	ret2 = isInterleave(s1, s2.substring(1), s3.substring(1));
	return ret1|ret2;
	}

view raw gistfile1.java hosted with ❤ by GitHub

However, it failed on large test cases in leetcode.

Naturally I resorted to DP.  The typical way of solving a problem with DP is to find the state, and the optimal function. Here, the state can be considered as: dp[i][j] meaning S3[i+j] can be formed by S1[i] and S2[j] (for simplicity here string starts from 1, in the code we need to deal with that string starts from 0). With the recursion code as in lines 43~47, it is easy to come up with the optimal function:
dp[i][j]=(dp[i-1][j]==true && s1.charAt(i-1)==s3.charAt(i+j-1))
              ||(dp[i][j-1]==true && s2.charAt(j-1)==s3.charAt(i+j-1) )

Note: the initial states require great care to populate as well as the index. See the code:
To run the code in your mind, simply use s1="a", s2="b", s3="ab" as an example.

	public boolean isInterleave(String s1, String s2, String s3) {
	int len1 = s1.length();
	int len2 = s2.length();
	int len3 = s3.length();
	if((len1+len2) != len3) return false;
	if(len1==0){
	if(s2.equals(s3))
	return true;
	else
	return false;
	}
	if(len2==0){
	if(s1.equals(s3))
	return true;
	else
	return false;
	}
	if(len3==0)
	{
	if(len1==0 && len2==0)
	return true;
	else
	return false;
	}
	boolean dp[][] = new boolean[len1+1][len2+1];
	dp[0][0]= true;
	for(int i=1; i<=len1; i++){
	if(dp[i-1][0] && s3.charAt(i-1)==s1.charAt(i-1))
	dp[i][0]=true;
	}
	for(int i=1; i<=len2; i++){
	if(dp[0][i-1] && s3.charAt(i-1)==s2.charAt(i-1))
	dp[0][i]=true;
	}
	for(int i=1; i<=len1; i++)
	for(int j=1; j<=len2; j++){
	dp[i][j]=(dp[i-1][j]==true && s1.charAt(i-1)==s3.charAt(i+j-1))||(dp[i][j-1]==true && s2.charAt(j-1)==s3.charAt(i+j-1));
	}
	return dp[len1][len2];
	}

view raw gistfile1.java hosted with ❤ by GitHub