检查一个字符串是否是其他两个给定的字符串

Question

的洗牌这是的算法设计问题手册：

假设你被赋予角色的三个字符串：X，Y，并且Z，其中|X| = n， |Y| = m，和|Z| = n+m.Z被说成是的X混洗和Y当且仅当Z可以通过从X和交织字符来形成以保持每个字符串中字符从左到右的顺序。

给出一个有效的动态规划算法，确定Z是否是X和Y的混洗。

提示：动态规划矩阵的你构建的价值观应该是布尔值，而不是数字

这是我的尝试：

起初，我做了一个1-d字符数组和指针X，Y，Z的起始字符。如果Z指针与char数组中的X指针存储X匹配，则使用Y指针检查相同的结果。如果char数组中的每个条目与其最后一个条目没有差异，则Z不交织。

有人可以帮我解决这个问题吗？

Answer 1

以下方法应该给你一个想法。

定义条件d(s1,s2,s3) = (s1 + s2 == s3) { s3 is a shuffle of s1 and s2 }

我们必须找到d(X, Y, Z)。

如果s1和s2的长度各自是和s3 = 2的长度为1，

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

同样D可为空字符串来获得。

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

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

可以计算d()条目从零个长度字符串开始并继续检查。

Answer 2

它由以下递推关系定义： -

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] 

你应该尝试这对你自己的代码为DP。

Answer 3

首先，让我们从一些定义开始。我写X[i]为i的X和X[i)的第012个元素，X的子字符串从索引i开始。

例如，如果X = abcde，则X[2] = c和X[2) = cde。

类似的定义适用于Y和Z。

---

为了解决动态规划问题，你应该保持尺寸(n+1) x (m+1)的2D布尔数组A。在此阵列中，A[i, j] = true当且仅当X[i)和Y[j)可以交错形成Z[i+j)。

对于任意(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] 

您拥有的情况下，二维数组的边缘，要么X或Y已经在其端部，这意味着其他的后缀应等于的Z后缀：

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

---

如果首先填充阵列的边界（A[m, j]和，对于所有的i, j），则可以简单地向A[0, 0]环回，并适当地设置条目。到底A[0, 0]是你的答案。

Answer 4

要点：

1. 所有字符串不应为null或空。
2. 2个字符串长度的总和应该等于第三个字符串。
3. 第三个字符串不应包含2个字符串的子字符串。
4. 否则创建字符数组，进行排序和比较。

代码：

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; 
}