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:
First try: use the first letter from s1 to match s3's first letter, if it doesn't match, use s2's.
It fails in the following case: s1="bb"; s2="ba" and s3="bbab". When we match s3's first two letters using s1, we can't match s3 using s2, however, s3 can be formed by s1 and s2.
The reason why my first try failed was that the approach ignored the case that s2's first letter can also match s3's first letter. Thus, all cases need to be saved.

Then, dynamic programming seems to be the best choice, since it caches all previous results.
dp[i][j] donates that if s3[1...i+j] can be interleaved by s1[1...i] and s2[1...j].
When it come to s3 = "bba", we check both s1="bb" & s2="b" and s1="b" & s2="ba".
Iteration formula: dp[i][j] = dp[i-1][j] && s1[i-1]==s3[i+j-1] ||
                                       dp[i][j-1] && s2[j-1]==s3[i+j-1]             //String index starts from 0.

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