文字列からの繰り返し文字の削除

投稿日: 2019-10-18 2022-10-15
タグ: Java, Java String

1. 概要

このチュートリアルでは、文字列から繰り返し文字を削除する方法について、Javaのいくつかのテクニックについて説明します。

それぞれの手法について、時間と空間の複雑さについても簡単に説明します。

2. distinctを使用する

Java8で導入されたdistinctメソッドを使用して、文字列から重複を削除することから始めましょう。

以下では、指定された文字列オブジェクトから Int S treamのインスタンスを取得しています。次に、distinctメソッドを使用して重複を削除します。最後に、 forEach メソッドを呼び出して、個別の文字をループし、それらをStringBuilderに追加します。

StringBuilder sb = new StringBuilder();
str.chars().distinct().forEach(c -> sb.append((char) c));

時間計算量： O（n） –ループの実行時間は入力文字列のサイズに正比例します

補助スペース： O（n） – distinctは内部でLinkedHashSetを使用し、結果の文字列もStringBuilderオブジェクト

順序を維持：はい– LinkedHashSetはその要素の順序を維持するため

そして、Java 8がこのタスクを非常にうまく実行してくれるのは素晴らしいことですが、それを私たち自身の努力と比較してみましょう。

3. indexOfを使用する

文字列から重複を削除する単純なアプローチでは、入力をループし、indexOfメソッドを使用して、結果の文字列に現在の文字がすでに存在するかどうかを確認します。

StringBuilder sb = new StringBuilder();
int idx;
for (int i = 0; i < str.length(); i++) {
    char c = str.charAt(i);
    idx = str.indexOf(c, i + 1);
    if (idx == -1) {
        sb.append(c);
    }
}

時間計算量： O（n * n） –文字ごとに、indexOfメソッドが残りの文字列を実行します

補助スペース： O（n） – StringBuilder を使用して結果を格納するため、線形スペースが必要です

順序を維持します：はい

この方法は、最初のアプローチと同じスペースの複雑さを持っていますが、のパフォーマンスははるかに遅くなります。

4. 文字配列の使用

文字列をchar配列に変換し、各文字をループして後続のすべての文字と比較することにより、文字列から重複を削除することもできます。

以下に示すように、2つの for ループを作成し、各要素が文字列内で繰り返されているかどうかを確認しています。重複が見つかった場合、それをStringBuilderに追加しません。

char[] chars = str.toCharArray();
StringBuilder sb = new StringBuilder();
boolean repeatedChar;
for (int i = 0; i < chars.length; i++) {
    repeatedChar = false;
    for (int j = i + 1; j < chars.length; j++) {
        if (chars[i] == chars[j]) {
            repeatedChar = true;
            break;
        }
    }
    if (!repeatedChar) {
        sb.append(chars[i]);
    }
}

時間計算量： O（n * n） –入力文字列を通過する内側ループと外側ループがあります

補助スペース： O（n） – chars 変数は文字列入力の新しいコピーを格納し、も使用しているため、線形スペースが必要です。 X164X]StringBuilderで結果を保存します

順序を維持します：はい

繰り返しになりますが、2回目の試行は、Core Java製品と比較してパフォーマンスが低くなりますが、次の試行でどこに到達するかを見てみましょう。

5. 並べ替えの使用

または、入力文字列を並べ替えて重複をグループ化することにより、繰り返される文字を削除することもできます。そのためには、文字列をchar配列に変換し、Arrays.sortメソッドを使用して並べ替える必要があります。最後に、ソートされたchar配列を繰り返し処理します。

すべての反復中に、配列の各要素を前の要素と比較します。要素が異なる場合は、現在の文字を StringBuilder：に追加します

StringBuilder sb = new StringBuilder();
if(!str.isEmpty()) {
    char[] chars = str.toCharArray();
    Arrays.sort(chars);

    sb.append(chars[0]);
    for (int i = 1; i < chars.length; i++) {
        if (chars[i] != chars[i - 1]) {
            sb.append(chars[i]);
        }
    }
}

時間計算量： O（n log n） –ソートはデュアルピボットクイックソートを使用し、多くのデータセットでO（n log n）パフォーマンスを提供します

補助スペース： O（n） – toCharArrayメソッドが入力Stringのコピーを作成するため

順序を維持します：いいえ

最後の試みでもう一度試してみましょう。

6. セットを使用する

文字列から繰り返し文字を削除する別の方法は、Setを使用することです。 出力文字列内の文字の順序を気にしない場合は、HashSetを使用できます。 それ以外の場合は、LinkedHashSetを使用して挿入順序を維持できます。

どちらの場合も、入力文字列をループして、各文字をSetに追加します。文字がセットに挿入されたら、それを繰り返して StringBuilder に追加し、結果の文字列を返します。

StringBuilder sb = new StringBuilder();
Set<Character> linkedHashSet = new LinkedHashSet<>();

for (int i = 0; i < str.length(); i++) {
    linkedHashSet.add(str.charAt(i));
}

for (Character c : linkedHashSet) {
    sb.append(c);
}

時間計算量： O（n） –ループの実行時間は入力文字列のサイズに正比例します

補助スペース： O（n） – Set に必要なスペースは、入力文字列のサイズによって異なります。また、StringBuilderを使用して結果を保存しています

順序を維持します： LinkedHashSet – はい、 HashSet –いいえ

そして今、私たちはコアJavaアプローチにマッチしました！これがdistinctがすでに行っていることと非常に似ていることを知るのはそれほどショックではありません。

7. 結論

この記事では、Javaで文字列から繰り返し文字を削除するいくつかの方法について説明しました。これらの各メソッドの時間とスペースの複雑さについても説明しました。

いつものように、コードスニペットはGitHubのにあります。

getdocs

13036