Given three strings:s1,s2,s3, determine whethers3_is formed by the interleaving of_s1_and_s2.

Have you met this question in a real interview?

Yes

Example

For s1 ="aabcc", s2 ="dbbca"

• When s3 = "aadbbcbcac" , return true .
• When s3 = "aadbbbaccc" , return false

假设
f[i][j] 为A的前i个字符 和 B的前j个字符是否是interleaving string

f[i][j] = (f[i - 1][j] && A[i - 1] == T[i + j - 1]) || (f[i][j - 1] && B[j - 1] == T[i + j - 1])

initialization
f[0][0] = true
f[0][i] = B[i - 1] == T[i - 1]
f[i][0] = A[i - 1] == T[i - 1]

public class Solution {
    /*
     * @param s1: A string
     * @param s2: A string
     * @param s3: A string
     * @return: Determine whether s3 is formed by interleaving of s1 and s2
     */
    public boolean isInterleave(String s1, String s2, String s3) {
        // write your code here

        if (s1 == null && s2 == null && s3 == null) {
            return true;
        }

        if (s1 == null || s2 == null || s3 == null || s1.length() + s2.length() != s3.length()) {
            return false;
        }

        boolean[][] f = new boolean[s1.length() + 1][s2.length() + 1];

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

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

        f[0][0] = true;

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

        return f[s1.length()][s2.length()];

    }
}