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.

Notes:

1. Double Sequence DP
2. State: f[i][j] the string s3 can be formed by the interleaving of s1[0..i] and s2[0..j]
3. Function: f[i][j] = s1.charAt(i-1) == s3.charAt(i+j-1) && f[i-1][j] || s2.charAt(j-1) == s3.charAt(i+j-1) && f[i][j-1].
   1. Compare the char, when char equals check the previous one which doesn't include this char
4. Initialize: f[0][0] = true. f[i][0] = s1.charAt(i-1) == s3.charAt(i-1) && f[i-1][0], f[0][i] = s2.charAt(i-1) == s3.charAt(i-1) && f[0][i-1];
5. Answer: f[m][n]

反复利用一个公式：如果在i，j处为true，那么必然是当s1[i] == s3[i+j-1]时，前一个位置也为true 或 s2[j] == s3[i+j-1]时，前一个位置也为true

    public boolean isInterleave(String s1, String s2, String s3) {
        if (s3 == null || (s1 == null && s2 == null)) {
            return false;
        }

        if (s1 == null || s1.isEmpty()) {
            return s3.equals(s2);
        }

        if (s2 == null || s2.isEmpty()) {
            return s3.equals(s1);
        }

        int m = s1.length();
        int n = s2.length();

        if (s3.length() != m+n) {
            return false;
        }

        // state
        boolean[][] f = new boolean[m+1][n+1];

        // initialize
        f[0][0] = true;

        for (int i = 1; i <= m; ++i) {
            f[i][0] = s1.charAt(i-1) == s3.charAt(i-1) && f[i-1][0];
        }

        for (int i = 1; i <= n; ++i) {
            f[0][i] = s2.charAt(i-1) == s3.charAt(i-1) && f[0][i-1];
        }

        // function
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                f[i][j] = s1.charAt(i-1) == s3.charAt(i+j-1) && f[i-1][j]
                    || s2.charAt(j-1) == s3.charAt(i+j-1) && f[i][j-1];
            }
        }

        // answer
        return f[m][n];
    }