检查字符串是否为其他两个给定字符串的洗牌。

This is a question from The Algorithm Design Manual:

这是算法设计手册中的一个问题:

Suppose you are given three strings of characters: X, Y, and Z, where |X| = n, |Y| = m, and |Z| = n+m. Z is said to be a shuffle of X and Y if and only if Z can be formed by interleaving the characters from X and Y in a way that maintains the left-to right ordering of the characters from each string.

假设你有三串字符:X, Y, Z，其中|X| = n， |Y| = m， |Z| = n+m。Z是一个洗牌的X和Y当且仅当Z可以由交叉X和Y的字符的方式维护留给订购每个字符串的字符。

Give an efficient dynamic programming algorithm that determines whether Z is a shuffle of X and Y.

给一个有效的动态编程算法,确定Z是X和Y的洗牌。

Hint: the values of the dynamic programming matrix you construct should be Boolean, not numeric

提示:您构造的动态规划矩阵的值应该是布尔型的，而不是数值型的。

This is what I tried:

这就是我所尝试的:

Initially, I made a 1-D char array and pointers to the starting characters of X,Y,Z respectively. If Z-pointer with matches X-pointer store X in the char array else check the same with Y-pointer.If each entry in the char array is not different from its last entry, Z is not interleaved.

最初，我分别对X、Y、Z的起始字符进行了1-D字符数组和指针。如果在char数组中与X指针相匹配的z指针，则用y指针检查相同的值。如果char数组中的每个条目与最后一个条目没有区别，那么Z就不会交叉。

Can someone help me with this problem?

有人能帮我解决这个问题吗?

4 个解决方案

#1

Following approach should give you an idea.

下面的方法会给你一个想法。

Define the condition d(s1,s2,s3) = (s1 + s2 == s3) { s3 is a shuffle of s1 and s2 }

定义条件d(s1,s2,s3) = (s1 + s2 == s3) {s3是s1和s2}的洗牌。

We have to find d( X, Y, Z ).

我们要找到d(X, Y, Z)

if lengths of s1 and s2 are 1 each and length of s3 = 2,

如果s1和s2的长度分别为1和s3 = 2，

d( s1,s2,s3 ) = { (s1[0] == s3[0] && s2[0] == s3[1]) || (s1[0] == s3[1] && s2[0] == s3[0])

Similarly d can be obtained for empty strings.

同样的d可以用于空字符串。

For strings of arbitrary length, following relation holds.

对于任意长度的字符串，以下关系成立。

d( s1,s2,s3 ) = { ( d( s1-s1[last],s2,s3 - s3[last]) && s1[last] == s3[last] )
                  || ( d( s1,s2 - s2[last],s3 - s3[last]) && s2[last] == s3[last] )
                }

You can compute the d() entries starting from zero length strings and keep checking.

您可以计算从零长度字符串开始的d()项，并继续检查。

#2

First, let's start with some definitions. I write X[i] for the ith element of X and X[i) for the substring of X starting at index i.

首先，让我们从一些定义开始。我把X[I]写在X和X的第I个元素上，从索引I开始。

For example, if X = abcde, then X[2] = c and X[2) = cde.

例如，如果X = abcde，那么X[2] = c和X[2] = cde。

Similar definitions hold for Y and Z.

对Y和Z也有类似的定义。

To solve the problem by dynamic programming, you should keep a 2D boolean array A of size (n+1) x (m+1). In this array, A[i, j] = true if and only if X[i) and Y[j) can be interleaved to form Z[i+j).

要用动态规划来解决这个问题，你应该保持一个二维布尔数组a的大小(n+1) x (m+1)。在这个数组中，A[i, j] = true，如果且仅当X[i]和Y[j]可以交错形成Z[i+j]。

For an arbitrary (i, j), somewhere in the middle of the 2D array, the recurrence relation is very simple:

对于任意(i, j)，在二维数组中间的某个地方，递归关系非常简单:

A[i, j] := X[i] = Z[i+j] and A[i+1, j]
        or Y[j] = Z[i+j] and A[i, j+1]

On the edges of the 2D array you have the case that either X or Y is already at its end, which means the suffix of the other should be equal to the suffix of Z:

在二维数组的边，你有一个例子，X或Y已经在它的末端，这意味着另一个的后缀应该等于Z的后缀:

A[m, j] := Y[j) = Z[m+j)
A[i, n] := X[i) = Z[i+n)
A[m, n] := true

If you first fill the border of the array (A[m, j] and A[i, n], for all i, j), you can then simply loop back towards A[0, 0] and set the entries appropriately. In the end A[0, 0] is your answer.

如果您首先填充数组的边界(A[m, j]和[i, n]，对于所有i, j)，那么您可以简单地返回到[0,0]，并适当地设置条目。最后A[0,0]是你的答案。

#3

It is defined by following recurrence relation:-

它由以下递归关系定义:-。

S(i,j,k) = false

if(Z(i)==Y(k))
  S(i,j,k) = S(i,j,k)||S(i+1,j,k+1)

if(Z(i)==X(j))
  S(i,j,k) = S(i,j,k)||S(i+1,j+1,k)

Where S(i,j,k) corresponds to Z[i to end] formed by shuffle of X[j to end] and Y[K to end]

You should try to code this into DP on your own.

您应该尝试自己将其编码到DP。

#4

-1

Key points:

重点:

All strings shouldn't be null or empty.
所有字符串不应该是空的。
The sum of the 2 strings length should be equal to the third string.
两个字符串长度的和应该等于第三个字符串。
The third string should not contain the substrings of the 2 strings.
第三个字符串不应该包含两个字符串的子字符串。
Else create arrays of characters , sort and compare.
其他创建字符数组，排序和比较。

Code:

代码:

public static boolean validShuffle(String first, String second, String third){
  boolean status=false;
  if((first==null || second==null || third==null) || (first.isEmpty()|| second.isEmpty() || third.isEmpty())){
    status = false;
  } else if((first.length()+second.length()) !=third.length()){
    //check if the sum of 2 lengths equals to the third string length
    status = false;
  } else if(third.indexOf(first,0)!=-1 || third.indexOf(second,0)!=-1){
    //check if the third string contains substrings
    status = false;
  } else {
    char [] c1_2=(first+second).toCharArray();
    char [] c3 =third.toCharArray();
    Arrays.sort(c1_2);
    Arrays.sort(c3);
    status=Arrays.equals(c1_2, c3);
  }
  return status;
}

#1