字符串交错的动态规划问题解决方案

我试图解决这个问题，但我放弃了，找到了下面的解决方案，尽管我不明白该解决方案是如何工作的，或者为什么它有效。任何深入的解决方案将不胜感激。

问题：

Given s1, s2, s3, 求是否s3由交错形成s1 and s2.

例如，给定：

s1 = "aabcc"
s2 = "dbbca"

• When s3 = "aadbbcbcac"，返回真。
• When s3 = "aadbbbaccc"，返回假。

解决方案：

  public static boolean isInterleave(String s1, String s2, String s3) {
        if (s3.length() == 0 && s1.length() == 0 && s2.length() == 0)
            return true;

        else if (s3.length() != s1.length() + s2.length())
            return false;
        boolean isInter[][] = new boolean[s1.length()+1][s2.length()+1];
        isInter[0][0] = true;
        for ( int i = 1; i <= s1.length(); ++i){
            if (s1.charAt(i-1) == s3.charAt(i-1))
                isInter[i][0] = true;
            else
                break;
        }
        for ( int i = 1; i <= s2.length(); ++i){
            if (s2.charAt(i-1) == s3.charAt(i-1))
                isInter[0][i] = true;
            else
                break;
        }
        // DP
        for ( int i = 1; i <= s1.length(); ++i){
            for ( int j = 1; j <= s2.length(); ++j){
                if (s3.charAt(i+j-1) == s1.charAt(i-1))
                    isInter[i][j] = isInter[i-1][j] || isInter[i][j];
                if (s3.charAt(i+j-1) == s2.charAt(j-1))
                    isInter[i][j] = isInter[i][j-1] || isInter[i][j];
            }
        }
        return isInter[s1.length()][s2.length()];
    }

我在这里使用 Python 切片语法，因为它很好。S[:-1]表示字符串S删除最后一个字符并且S[:n]表示前缀S有长度的n.

关键的想法是如果C是一个交错A and B, then C[:-1]是一个交错A and B[:-1] or of A[:-1] and B。另一方面，如果C是一个交错A and B, then C + 'X'是一个交错A + 'X' and B这也是一个交错的A and B + 'X'.

这些是我们应用动态规划所需的子结构属性。

我们定义f(i, j) = true, if s1[:i] and s2[:j]可以交错形成s3[:(i+j)] and f(i,j) = false否则。通过上面的观察我们有

f(0,0) = true
f(i,0) = f(i-1, 0) if s3[i-1] == s1[i-1]
f(0,j) = f(0, j-1) if s3[j-1] == s2[j-1]
f(i,j) = true if s3[i+j-1] = s1[i-1] and f(i-1, j)
f(i,j) = true if s3[i+j-1] = s2[j-1] and f(i, j-1)

在所有其他情况下，我们有f(i,j) = false。 Java代码只是使用动态编程来实现这种递归。也就是说，我会以更简洁的方式实现它：

for (int i = 0; i <= s1.length(); ++i)
    for (int j = 0; j <= s2.length(); ++j)
        isInter[i][j] = (i == 0 && j == 0)
           || (i > 0 && s1.charAt(i-1) == s3.charAt(i+j-1) && isInter[i-1][j])
           || (j > 0 && s2.charAt(j-1) == s3.charAt(i+j-1) && isInter[i][j-1]);