〔アルゴリズム〕2つの文字列が同じ文字で構成されているか否かを判断する

2つの文字列が同じ文字で構成されているかどうかを判断する方法

タイトルの説明:
同じ文字で構成されているとは、2つの文字列を構成する文字と、各文字の個数が同じで、配列順序が異なるだけです.例えば「aaaabbc」と「abcbaaa」は同じ文字からなる.
方法1:
ソート法では、2つの文字列の文字をソートし、2つのソート後の文字列が等しいかどうかを比較します.等しい場合は、同じ文字で構成されていることを示します.そうでない場合は、異なる文字で構成されていることを示します.

import java.util.Arrays;

public class Solution {

    public static void compare(String s1,String s2){
        byte[] b1 = s1.getBytes();
        byte[] b2 = s2.getBytes();
        Arrays.sort(b1);
        Arrays.sort(b2);
        s1 = new String(b1);
        s2 = new String(b2);
        if(s1.equals(s2)){
            System.out.println("equal");
        }else {
            System.out.println("not equal");
        }
    }

    public static void main(String[] args) {
        String s1 = "aaaabbc";
        String s2 = "abcbaaa";
        compare(s1, s2);
        s1 = "aaaabbc";
        s2 = "abcbaab";
        compare(s1, s2);
    }
}

以上の方法はソートアルゴリズムの時間的複雑度に依存し,最も速いソートアルゴリズムの時間的複雑度はO(nlogn)であるため,この方法の時間的複雑度もO(nlogn)である.
方法2:
スペースチェンジ時間は、文字列がASCAII文字のみを使用すると仮定し、ASCAII文字は266個(対応する符号化は0~255)しかないため、実装時にサイズ266の配列を申請することで各文字の出現個数を記録し、0に初期化した後、最初の文字列を遍歴し、文字列中の文字に対応するASCII符号値を配列下標として対応する配列の要素に1を加え、2番目の文字列を遍歴し、配列内の対応する要素値-1を最後の配列の各要素の値が0の場合、この2つの文字列は同じ文字で構成されていることを示します.そうでなければ、この2つの文字列が異なる文字で構成されていることを示します.
コードは次のとおりです.

package                  ;

public class Solution1 {

    public static void compare(String s1, String s2) {
        byte[] b1 = s1.getBytes();
        byte[] b2 = s2.getBytes();
        int[] bCount = new int[256];
        for (int i = 0; i < 256; i++) {
            bCount[i] = 0;
        }
        for (int i = 0; i < b1.length; i++) {
            bCount[b1[i] - '0']++;
        }
        for (int i = 0; i < b2.length; i++) {
            bCount[b2[i] - '0']--;
        }

        for (int i = 0; i < 256; i++) {
            if (bCount[i] != 0) {
                System.out.println("not equal");
                return;
            }
        }
        System.out.println("equal");
    }


    public static void main(String[] args) {
        String s1 = "aaaabbc";
        String s2 = "abcbaaa";
        compare(s1, s2);
        s1 = "aaaabbc";
        s2 = "abcbaab";
        compare(s1, s2);
    }
}

方法二時間複雑度はO(n)であったが,余分な空間を申請した.