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 m1 = s1.length();
        int m2 = s2.length();
        int m3 = s3.length();

        if (m1 + m2 != m3) {
            return false;
        }

        boolean[][] matches = new boolean[m1 + 1][m2 + 1];
        for (int i = 0; i <= m1; i++) {
            for (int j = 0; j <= m2; j++) {
                if (i == 0 && j == 0) matches[i][j] = true;
                else if (i == 0) matches[i][j] = matches[i][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
                else if (j == 0) matches[i][j] = matches[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i - 1);
                else {
                    matches[i][j] = (matches[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) ||
                            (matches[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
                }
            }
        }

        return matches[m1][m2];
    }
}