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:

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