codewars合併字符串檢查器

Question

在求職面試中，您面臨的挑戰是編寫一個算法來檢查給定字符串s是否可以由其他兩個字符串part1和part2組成。

限制是part1和part2中的字符與s中的字符順序相同。

面試官給你下面的例子，告訴你從給定的測試用例中找出其餘的部分。

例如：

'codewars' 是 'CDW' 和 'oears' 合併：

參見：https://www.codewars.com/kata/merged-string-checker/train/java

這是我的Java代碼，但無法通過所有測試請問，哪裏錯了？謝謝！

public static boolean isMerge(String s, String part1, String part2) { 
    s = s.replace(" ",""); 
    part1 = part1.replace(" ",""); 
    part2 = part2.replace(" ",""); 

    int index1 = 0; 
    int index2 = 0; 

    char[] cp1 = part1.toCharArray(); 
    char[] cp2 = part2.toCharArray(); 

    for (int i = 0; i < s.length();) { 
     char is = s.charAt(i); 
     if (index1 < cp1.length && cp1[index1] == is) { 
      index1++; 
      i++; 
      continue; 
     } 
     if (index2 < cp2.length && cp2[index2] == is) { 
      index2++; 
      i++; 
      continue; 
     } 
     return false; 
    } 
    return s.length() == index1 + index2; 
} 

Answer 1

的問題是，例如，如果您有：

S = cdwzzzcdw

第一部分= CDW

第2部分= cdwzzz

什麼情況是，第一次嘗試將整個part1與S的開頭相匹配，部分將不能匹配字符串的其餘部分。但是，如果你首先考慮了第二部分，那麼它將被正確地完成。

所以，底線是你應該考慮所有的可能性。我假設一個dyanmic編程方法會起作用。這是C++中的一個僞代碼：

bool rec(idx1, idx2, idxS){ 
    if(idx1 == part1.length && idx2 == part2.length){ 
     if(idxS == S.length) return true; //everything matched 
     return false; //S has remaining 

    } 
    if(idxS == S.length){ //length part1 + part2 is more than S 
     return false; 
    } 
    if(mark[idx1][idx2][idxS] == true) //computed before 
     return dp[idx1][idx2][idxS]; 

    mark[idx1][idx2][idxS] = true; 
    dp[idx1][idx2][idxS] = false; 

    if(idx1 < part1.length && part1[idx1] == S[idxS]){ 
     if(rec(idx1 + 1, idx2, idxS + 1) == true) { 
      dp[idx1][idx2][idxS] = true; 
     } 
    } 
    if(idx2 < part2.length && part2[idx2] == S[idxS]){ 
     if(rec(idx1, idx2 + 1, idxS + 1) == true){ 
      dp[idx1][idx2][idxS] = true; 
     } 
    } 
    return dp[idx1][idx2][idxS]; 
}