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.

Understand the problem:
The problem gives three strings s1, s2, and s3, find out whether s3 is formed by the interleaving of s1 and s2. The crux of the problem is to understand the "interleaving". Basically, we can understand the problem by s2 is formed by connecting s1 and s2 together. The way of connecting could be interleaved. 

DP Solution:
We can use DP to solve this problem. So the steps are:

• Define boolean dp[str1.length() + 1][str2.length() + 1], where dp[ i ][ j ] : means whether str1.charAt(0) to str1.charAt(i) and str2.charAt(0) to str2.charAt(j) could construct the string str3, from 0 to i + j. 
• Transit function: 
• dp[i][j]  = str3.charAt(i + j) == str1.charAt(i) && dp[ i - 1][j] || 
• str3.charAt(i + j) == str2.charAt(j) && dp[i][j - 1]
• Initial State 
• dp[0][0] = true;
• dp[0][j] = str3.charAt(j) == str2.charAt(j)
• dp[i][0] = str3.charAt(i) == str1.charAt(i)
• Final state dp[str1.length()][str2.length()]. 

Code (Java):

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