2つの文字列がJavaのアナグラムであるかどうかを確認します

投稿日: 2022-10-16 2022-10-16
タグ: Java, Java String

1. 概要

Wikipedia によると、アナグラムは、別の単語またはフレーズの文字を再配置することによって形成された単語またはフレーズです。

これを文字列処理で一般化するには、文字列のアナグラムは、各文字の量が任意の順序でまったく同じである別の文字列であると言うことができます。

このチュートリアルでは、スペースや数字などの非英字を含む、各文字の量が等しくなければならない文字列アナグラム全体の検出について説明します。たとえば、「！low-salt！」 と「フクロウ-lat!!」 はまったく同じ文字が含まれているため、アナグラムと見なされます。

2. 解決

2つの文字列がアナグラムであるかどうかを判断できるいくつかのソリューションを比較してみましょう。各ソリューションは、最初に2つの文字列の文字数が同じかどうかを確認します。異なる長さの入力をアナグラムにすることはできないため、これは早期に終了するための簡単な方法です。

考えられる解決策ごとに、開発者としての実装の複雑さを見てみましょう。また、 big O表記を使用して、CPUの時間計算量についても見ていきます。

3. 並べ替えで確認

文字を並べ替えることで、各文字列の文字を再配置できます。これにより、2つの正規化された文字配列が生成されます。

2つの文字列がアナグラムの場合、正規化された形式は同じである必要があります。

Javaでは、最初に2つの文字列を char[]配列に変換できます。次に、これら2つの配列を並べ替えて、等しいかどうかを確認します。

boolean isAnagramSort(String string1, String string2) {
    if (string1.length() != string2.length()) {
        return false;
    }
    char[] a1 = string1.toCharArray();
    char[] a2 = string2.toCharArray();
    Arrays.sort(a1);
    Arrays.sort(a2);
    return Arrays.equals(a1, a2);
}

このソリューションは、理解と実装が簡単です。ただし、 n 文字の配列の並べ替えにはO（n log n）時間がかかるため、このアルゴリズムの全体的な実行時間は O（n log n）です。

アルゴリズムが機能するには、少し余分なメモリを使用して、両方の入力文字列のコピーを文字配列として作成する必要があります。

4. カウントして確認

別の戦略は、入力内の各文字の出現回数をカウントすることです。 これらのヒストグラムが入力間で等しい場合、文字列はアナグラムです。

少しのメモリを節約するために、ヒストグラムを1つだけ作成しましょう。最初の文字列の各文字のカウントをインクリメントし、2番目の文字列の各文字のカウントをデクリメントします。 2つの文字列がアナグラムの場合、結果はすべてが0にバランスすることになります。

ヒストグラムには、文字セットサイズで定義されたサイズのカウントの固定サイズテーブルが必要です。たとえば、各文字を格納するために1バイトのみを使用する場合、256のカウント配列サイズを使用して各文字の出現をカウントできます。

private static int CHARACTER_RANGE= 256;

public boolean isAnagramCounting(String string1, String string2) {
    if (string1.length() != string2.length()) {
        return false;
    }
    int count[] = new int[CHARACTER_RANGE];
    for (int i = 0; i < string1.length(); i++) {
        count[string1.charAt(i)]++;
        count[string2.charAt(i)]--;
    }
    for (int i = 0; i < CHARACTER_RANGE; i++) {
        if (count[i] != 0) {
            return false;
        }
    }
    return true;
}

このソリューションは、 O（n）の時間計算量でより高速になります。ただし、カウント配列用に余分なスペースが必要です。 256整数の場合、ASCIIの場合はそれほど悪くありません。

ただし、UTF-8などの複数バイトの文字セットをサポートするために CHARACTER_RANGE を増やす必要がある場合、これは非常にメモリを消費します。したがって、可能な文字数が少ない場合にのみ実用的です。

開発の観点から、このソリューションには、維持するコードが多く含まれており、Javaライブラリ関数の使用が少なくなっています。

5. MultiSetで確認してください

MultiSet を使用すると、カウントと比較のプロセスを簡素化できます。 MultiSet は、重複する要素を使用した順序に依存しない同等性をサポートするコレクションです。たとえば、多重集合{a、a、b}と{a、b、a}は等しいです。

Multiset を使用するには、最初にGuava依存関係をプロジェクトpom.xmlファイルに追加する必要があります。

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.0.1-jre</version>
</dependency>

各入力文字列をMultiSetの文字に変換します。次に、それらが等しいかどうかを確認します。

boolean isAnagramMultiset(String string1, String string2) {
    if (string1.length() != string2.length()) {
        return false;
    }
    Multiset<Character> multiset1 = HashMultiset.create();
    Multiset<Character> multiset2 = HashMultiset.create();
    for (int i = 0; i < string1.length(); i++) {
        multiset1.add(string1.charAt(i));
        multiset2.add(string2.charAt(i));
    }
    return multiset1.equals(multiset2);
}

このアルゴリズムは、大きなカウント配列を宣言することなく、 O（n）時間で問題を解決します。

これは、前のカウントソリューションに似ています。ただし、固定サイズのテーブルを使用してカウントするのではなく、 MutlitSet クラスを利用して、各文字のカウントを使用して可変サイズのテーブルをシミュレートします。

このソリューションのコードは、カウントソリューションよりも高レベルのライブラリ機能をより多く利用しています。

6. 文字ベースのアナグラム

これまでの例は、アナグラムの言語学的定義に厳密に準拠していません。これは、句読点がアナグラムの一部であると見なされ、大文字と小文字が区別されるためです。

文字ベースのアナグラムを有効にするためにアルゴリズムを適応させましょう。空白や句読点などの他の文字に関係なく、大文字と小文字を区別しない文字の再配置のみを検討しましょう。たとえば、「小数点」および「私は所定の位置にドットです。」 はお互いのアナグラムになります。

この問題を解決するには、最初に2つの入力文字列を前処理して、不要な文字を除外し、文字を小文字に変換します。次に、上記のソリューションの1つ（たとえば、 MultiSet ソリューション）を使用して、処理された文字列のアナグラムをチェックできます。

String preprocess(String source) {
    return source.replaceAll("[^a-zA-Z]", "").toLowerCase();
}

boolean isLetterBasedAnagramMultiset(String string1, String string2) {
    return isAnagramMultiset(preprocess(string1), preprocess(string2));
}

このアプローチは、アナグラム問題のすべての変形を解決するための一般的な方法です。たとえば、数字も含める場合は、前処理フィルターを調整するだけです。

7. 結論

この記事では、特定の文字列が別の文字のアナグラムであるかどうかを確認するための3つのアルゴリズムについて説明しました。ソリューションごとに、必要なメモリの速度、読みやすさ、サイズの間のトレードオフについて説明しました。

また、より伝統的な言語の意味でアナグラムをチェックするためにアルゴリズムを適応させる方法についても検討しました。これは、入力を小文字に前処理することで実現しました。

いつものように、記事のソースコードはGitHubでから入手できます。

getdocs

13036