Java - 文字列の配列 - 特定の要素が他の文字列のPARTであるかどうかを確認します（ "Duplicates"をfinidngしない）

Question

Stringの配列を持ち、Stringの一部として他の文字が含まれているかどうか確認したい。

たとえば、単純な配列に従うことを検討してください。最後に

s[0]="Java" 
s[1]="Java Programming" 
s[2]="C Programming" 
s[3]="C Programming is Cool" 

S [1]はSを含んでいるので、私は[0]、S

s[1]="Java Programming" 
s[3]="C Programming is Cool" 

を保持する[3] [2] Sを含有します。

この

は、配列要素がString.Contains本当に基本的な非効率的なようだ（）メソッドを使用して、配列の要素が含まれている場合..

int startPtr = 0; 
while (startPtr < s.length-1) { 
    int tempPtr = startPtr+1; 
    while (tempPtr <= s.length-1) { 
     if (s[tempPtr].contains(s[startPtr])) { 
      //At this point, I know that I don't need s[startPtr] in result. 
      //Remove item at startPtr, if this were ArrayList or something. 
      startPtr++; 
      break; 
    } else { indexPtr++; } 
} 

を検出するために私のコードで、startPtrが最後に到達した後、私は私が持っていると思います逆の順序で同じことを行い（最後から始め、配列の先頭に向かってチェックする）、文字列が他の文字列要素の一部でないことを確認します。

もっと良いアルゴリズムを教えてもらえますか？ また、このalogirthmはO（N^2）を持つと私は正しいと思いますか？

Answer 1

OPはmapeterの答えに関する私のコメントについてより多くの情報を要求したので、私は答えとしてこれに応答しています。繰り返して言うと、Mapeterのソリューションの鍵は、リストから削除するのではなく、新しいリストにアイテムを追加することです。削除されたアイテムがポインタの算術演算を混乱させず、範囲外のエラーを引き起こさないようにします。しかしながら、これは、逆に配列を反復することにより、所定の位置で行うことができる。プリミティブ配列のサイズを固定されているので、もちろん

Collections.sort(s, new LengthCompare()); 
for (int i = s.size() - 1; i >= 1; i--) 
{ 
    for (int j = i-1; j >= 0; j--) 
    { 
     if (s[j].contains(s[i])) 
     { 
      s.remove(i) 
      break; 
     } 
    } 
} 

private static class LengthCompare implements Comparator<String> 
{ 
    public int compare(String s1, String s2) 
    { 
     return (s2.length() - s1.length()); 
    } 
} 

、これは、コードの残りの部分を見ることなく（リストのためのみですこれは、なぜあなたが1つを使用できなかったかわかりません）。

また、私はこれが実際にコンパイルされるかどうかを確認するためにテストしていません。これは単なる擬似コードなので、配列型とリスト型が混在している可能性がありますが、フォームは同じです。

Answer 2

文字列を長さの小さい順に並べ替えることをお勧めします。s後でsを反復するとき、後の文字列の長さがより短いため、各文字列を後の文字列sに含めることはできません。結果として、sまで一度だけ反復する必要があり、バックトラックを実行する必要はありません。

List<String> finalStrs = new ArrayList<>(); 
// You will have to create decreasingLengthComparator 
Arrays.sort(s, decreasingLengthComparator); 
for (String str : s) { 
    boolean addToFinal = true; 
    for (String finalStr : finalStrs) { 
     if (finalStr.contains(str)) { 
      addToFinal = false; 
      break; 
     } 
    } 
    if (addToFinal) { 
     finalStrs.add(str); 
    } 
} 

ソートの効率はO（nlog（n））です。 sを反復し、文字列がfinalStrsであるかどうかを確認する効率は、O（n^2/2）* O（文字列比較の時間）です。

結果として、全体の複雑さは、文字列比較の場合O（nlog（n）+ n^2/2 *時間）= O（n^2/2 *文字列比較の時間）あなたのアルゴリズムは（非常にわずかな改善ですが、アルゴリズムは実装が容易であり、私の意見に従います）。

Answer 3

大きな文字列と比較的短い文字列の別の可能性があります。計算の複雑さはO（n log（n）+ n k^2 * log（n * k））です。ここでnは文字列の数、kは最長文字列の長さです。

考えられるのは、既に結果セットに含まれている可能性のある文字列のすべての部分文字列のルックアップセットを作成し、このセットに存在を確認することです。

ルックアップセットにn * k^2/2の異なる文字列があります。

TreeSet<String> containedStrings = new TreeSet<>(); 
List<String> finalStrs = new ArrayList<>(); 
// You will have to create decreasingLengthComparator 
Arrays.sort(s, decreasingLengthComparator); 
for (String str : s) 
    if (!containedStrings.contains(str)) 
     finalStrs.add(str); 
     for (int i = 0; i < s.length(); i++) 
      for (int j = i+1; j <= s.length(); j++) 
       containedStrings.add(s.substring(i, j)); 
    }