コードワードでマージされた文字列チェッカー

Question

就職インタビューでは、指定された文字列sが2つの他の文字列part1とpart2から形成できるかどうかを確認するアルゴリズムを書くことに挑戦します。

part1とpart2の文字は、sと同じ順序であるという制約があります。

インタビュアーは、次の例を挙げて、残りのテストケースを把握するように指示します。例えば

：

'codewarsは' 'CDW' と 'oears' からのマージです：

参照：これはhttps://www.codewars.com/kata/merged-string-checker/train/java

私のJavaコードですが、すべてのテストに合格しませんでしたどこか間違っていますか？ありがとう！

S = cdwzzzcdw

パート1 = CDW

その2 = cdwzzz

を何が起こることはまずあなたがしようということである。

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

問題は、たとえば、あなたが持っている場合ということですpart1全体をSの先頭に一致させ、partは残りの文字列と一致することはできません。しかしpart2を最初に考えた場合、それは適切に行われます。

したがって、結論はすべての可能性を考慮する必要があるということです。私はダイナミックプログラミングアプローチがうまくいくと考えています。 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]; 
}