檢查一個字符串是否是其他兩個給定的字符串

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