はじめに

与えられた2つの文字列が互いに並び替えの関係にあるかどうかを判定するアルゴリズムの紹介です。具体的には、対象Aと対象Bの各々の文字列において、各々の文字列は文字の順序が入れ替わっているだけなのかを判定するアルゴリズムを学習したのでアウトプットします。

例題

trueの場合
A = ABC123
B = A32BC1

falseの場合
A = ABC123
B = D32BC1

アルゴリズムの概要

文字列の長さが異なる場合は並び替えの関係になりえないため、falseを返します。
文字列を構成する各文字の出現回数をカウントします。
2つの文字列のカウント結果を比較し、異なる文字の出現回数があればfalseを返します。
全ての文字の出現回数が一致していれば、文字列は並び替えの関係にあると判定し、trueを返します。

実装したコード



public class Task {

    public static void main(String[] args) {
        String str1 = "waterbottle";
        String str2 = "erbottlewat";
        System.out.println(isRotation(str1, str2));
    }

    public static boolean isSubstring(String s1, String s2) {
        return s1.matches(".*" + s2 + ".*$");
    }

    /* ここにisRotationメソッドを定義 */
    public boolean isRotation(String s, String t) {
        if (s.length() != t.length()) {
            //　文字列の長さが異なる場合、並び替えの関係ではない
            return false;
        }

        // ASCII文字の範囲(0から127)の要素数を持つ配列を作成
        int[] count = new int[128];

        // 文字列sの各文字の出現回数をカウント
        for (int i = 0; i < s.length(); i++) {
            // 出現した文字の数をcharAtメソッドで1文字ずつ取得しカウントする

            char ch = s.charAt(i);
            count[ch]++;
        }

        // 文字列tの各文字の出現回数をカウントし、出現回数を減算する
        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            count[ch]--;
            if (count[ch] < 0) {
                // 出現回数がマイナスになった場合、文字列tにsに存在しない文字が含まれるためfalseを返す
                return false;
            }
        }

        // すべての文字の出現回数が0であれば、文字列sとtは並び替えの関係にあると判定する
        return true;
    }
}

まとめ

今回はJavaで文字列の並び替えを検査する方法について解説しました。文字列の並び替えは、プログラミングでよく見られる基礎的な問題かと思います。もし必要であれば参考になれば幸いです