动态规划交错字符串+合并“噪声”
类似问题：交错字符串的动态规划问题解
我正在实现一个动态程序，它可以发现两个字符串s1和s2是否是一个较大字符串s的交错。
简单示例：s1=“ac”s2=“dbbca”s3=“aadbbcac”返回true
关键是我需要捕捉更大的s3字符串中的任何“噪波”，并指出噪波所在的位置。
例如：s1=“ac”s2=“dbbca”s3=“11aadbbcac11”s索引1,2,13,14处的噪声
我还需要捕获s3中的s1和s2字符串索引。
噪音也可以散布在弦之间
例如：
s1=“ac”s2=“dbbca”s3=“ac11dbbcca11”s3索引1,2,3,4,5处的s1 s3索引8,9,10,11,12处的s2 s3索引6,7,13,14处的噪声
我的问题是：如何在我的算法中加入“噪声”元素？我必须有一个比[s1.length]和[s2.length]的2d数组更大的搜索索引——但我现在无法理解它的实际外观。另外-我如何回溯我的动态程序，找出s1和s2的哪些元素被选为交织字符串s3的一部分？

public class Main {

public static void main(String[] args) {

    test("aabcc", "dbbca", "aadbbcbcac");
}

static void test(String s1, String s2, String s3){

    if (is_Interleave(s1,s2,s3)){
        System.out.println(s3 + " is interleaved of " + s1 + " and " + s2);
    }
    else{
        System.out.println(s3 + " is not interleaved of " + s1 + " and " + s2);
    }

}

public static boolean is_Interleave(String s1, String s2, String s3) {

    if (s3.length() != s1.length() + s2.length()) {
        return false;
    }
    boolean dp[][] = new boolean[s3.length() + 1][s3.length() + 1];

    for (int i = 0; i <= s1.length(); i++) {
        for (int j = 0; j <= s2.length(); j++) {

            if (i == 0 && j == 0) {
                dp[i][j] = true;
            }

            else if (i == 0) {
                dp[i][j] = dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
            }

            else if (j == 0) {
                dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
            }

            else {
                dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
                        || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));

            }

        }
    }

    return dp[s1.length()][s2.length()];
}

}