动态编程问题解决方案，解决交织字符串 [英] Dynamic programming problems solution to interleaving strings

问题描述

尽管我不了解该解决方案的工作原理或原因，但我一直试图解决此问题，但我放弃了，找到了下面的解决方案.任何深入的解决方案将不胜感激.

I was trying to solve this problem, and I gave up, and found the solution below, although I do not understand how the solution works, or why it works. Any in-depth solution would be deeply appreciated.

问题:

给出 s1 ， s2 ， s3 ，找出 s3 是否由的交织形成s1 和 s2 .

例如，给定:

s1 = "aabcc"
s2 = "dbbca"

• 当 s3 ="aadbbcbcac" 时，返回true.
• 当 s3 ="aadbbbaccc" 时，返回false.
• 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()];
    }

推荐答案

我在这里使用Python slice语法，因为它很不错. S [:-1] 表示除去最后一个字符的字符串 S ， S [:n] 表示 S的前缀的长度为 n .

I'm using Python slice syntax here because it is nice. S[:-1] means the string S with its last character removed and S[:n] means the prefix of S that has length n.

关键思想是，如果 C 是 A 和 B 的交织，则 C [:-1] 是 A 和 B [:-1] 的交织，或者是 A [:-1] 和 B的交织.另一方面，如果 C 是 A 和 B 的交织，则 C +'X'为 A +'X'和 B 的交织，它也是 A 和 B +'X'的交织代码>.

The key idea is that if C is an interleaving of A and B, then C[:-1] is either an interleaving of A and B[:-1] or of A[:-1] and B. On the other hand, if C is an interleaving of A and B, then C + 'X' is an interleaving of A + 'X' and B and it is also an interleaving of A and B + 'X'.

这些是我们应用动态编程所需的子结构属性.

These are the substructure properties we need to apply dynamic programming.

如果 s1 [:i] 和 s2 [:j] 可以交错，则我们定义 f(i，j)= true 形成 s3 [:( i + j)] ，否则形成 f(i，j)= false .通过上面的观察，我们已经

We define f(i, j) = true, if s1[:i] and s2[:j] can be interleaved to form s3[:(i+j)] and f(i,j) = false otherwise. By the observation above we have

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代码只是使用动态编程来实现这种重复.也就是说，我将以更简洁的方式实现它:

In all the other cases we have f(i,j) = false. The Java code just implements this recurrence using dynamic programming. That said, I would implement it in a bit more concise way:

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

这篇关于动态编程问题解决方案，解决交织字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！