今回は前回の続きといいますか、似たような問題に対する実装を複数パターンあったのでその速度を比較してみました。

問題

二つの文字列が与えられた時、片方がもう片方の並び替えになっているかどうかを決定するメソッドを書いてください。

前提条件：空白や大文字小文字も区別する。文字コードはASCIIコードだけで構わない。

というわけで書いてみました。

実装コード

static boolean MyisAnagram(String word1,String word2){
        int sumCode_1=0;
        int sumCode_2=0;
        
        if(word1.length()!=word2.length())
            return false;
        
        for(int i=0;i<word1.length();i++){
            sumCode_1 += word1.charAt(i);
        }
        for(int i=0;i<word2.length();i++){
            sumCode_2 += word2.charAt(i);
        }
        
        if(sumCode_1 == sumCode_2){
            return true;
        }
        else{
            return false;
        }
        
    }

あ、今回はjavaです。Eclipseで書いているので書いてる途中に間違えがすぐわかるので便利です。

上記のコードは自分が完全に０から考えたメソッドです。

文字列の文字コードを全て足し合わせて一致しているならアナグラムであると言えます。

中々スマートに書けたかなとは思います。

次に解答例としてあった二つの実装パターンをご紹介します。

static String sort(String s){
        char[] content = s.toCharArray();
        java.util.Arrays.sort(content);
        return new String(content);
    }
    
    static boolean permutation(String s,String t){
        if(s.length() != t.length()){
            return false;
        }
        return sort(s).equals(sort(t));
    }

static boolean permutation_2(String s,String t){
        if(s.length() != t.length()){
            return false;
        }
        
        int[] letters = new int[256]; //文字コードの仮定;
        
        char[] s_array = s.toCharArray();  
        for(char c:s_array){
            letters[c]++;
        }
        
        for(int i=0;i<t.length();i++){
            int c = (int)t.charAt(i);
            if(--letters[c] < 0){
                return false;
            }
        }
        return true;
    }

１個目はsortメソッドを作成し、二つの文字列を整列してから比較しています

２個目のメソッドは文字コードのリストをboolで作って出現したら1に、二個目の文字列を判定して、存在したら-1して0より小さくなったらその時点でfalseというのは面白いですね。

比較結果

メインメソッドを以下のように実装し実行時間を計ってみました。

public static void main(String[] args){
        long start = System.nanoTime();
        MyisAnagram("word","wo rd");
        MyisAnagram("word","fugafuga");
        MyisAnagram("word","rdow");
        long end = System.nanoTime();
        System.out.println("Processing time:" + (end - start) + "ns");
        
        start = System.nanoTime();
        permutation("word","wo rd");
        permutation("word","fugafuga");
        permutation("word","rdow");
        end = System.nanoTime();
        System.out.println("Processing time:" + (end - start) + "ns");
        
        start = System.nanoTime();
        permutation_2("word","wo rd");
        permutation_2("word","fugafuga");
        permutation_2("word","rdow");
        end = System.nanoTime();
        System.out.println("Processing time:" + (end - start) + "ns");
    }