给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

示例 1:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"输出: true

示例 2:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"输出: false

class Solution {    public boolean isInterleave(String s1, String s2, String s3) {        if (s1 == null || s2 == null || s3 == null || s3.length() != (s1.length() + s2.length()))            return false;        else if (s1.equals("") && s2.equals(s3) || s2.equals("") && s1.equals(s3))            return true;        int[][] dp = new int[s1.length() + 1][s2.length() + 1];        char[] chs1 = s1.toCharArray();        char[] chs2 = s2.toCharArray();        char[] chs3 = s3.toCharArray();        for (int i = 1; i <= chs1.length; i++) {            if (chs1[i - 1] == chs3[i - 1])                dp[i][0] = dp[i - 1][0] + 1;            else {                int t = dp[i - 1][0];                while(i < chs1.length) {                    dp[i - 1][0] = t;                    i++;                }            }        }        for (int i = 1; i <= chs2.length; i++) {            if (chs2[i - 1] == chs3[i - 1])                dp[0][i] = dp[0][i - 1] + 1;            else {                int t = dp[0][i - 1];                while(i < chs2.length) {                    dp[0][i - 1] = t;                    i++;                }            }        }        for (int i = 1; i <= chs1.length; i++) {            for (int j = 1; j <= chs2.length; j++) {                int ti = dp[i - 1][j];                int tj = dp[i][j - 1];                int t1 = ti + (chs1[i - 1] == chs3[ti] ? 1 : 0);                int t2 = tj + (chs2[j - 1] == chs3[tj] ? 1 : 0);                dp[i][j] = t1 > t2 ? t1 : t2;            }        }        return dp[chs1.length][chs2.length] == chs3.length;    }}