java - 交织字符串的动态规划问题解决方案

Question

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

问题:

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.

解决方法:

  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()];
    }

Answer 1

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

关键思想是如果C是 A 的交错和 B , 然后 C[:-1]是 A 的交错和 B[:-1]或 A[:-1]和 B .另一方面，如果 C是 A 的交错和 B , 然后 C + 'X'是 A + 'X' 的交错和 B也是A的交错和 B + 'X' .

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

我们定义f(i, j) = true , 如果 s1[:i]和 s2[:j]可以交错形成s3[:(i+j)]和 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]);