动态编程问题解决方案，解决交织字符串

本文介绍了动态编程问题解决方案，解决交织字符串的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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