2つの文字列の共通文字をアルファベット順に出力するJavaプログラム

2つの文字列に共通する文字を抽出し、アルファベット順(昇順)で出力するJavaプログラムを紹介します。このアプローチでは、各文字の出現回数を記録する「頻度配列」を利用することで、効率よく共通文字を求めることができます。

サンプルコード

import java.io.*;
import java.util.*;
public class Demo{
    static void common_chars(String str_1, String str_2){
        int[] array_1 = new int[26];
        int[] array_2 = new int[26];
        int str_len_1 = str_1.length();
        int str_len_2 = str_2.length();
        for (int i = 0 ; i < str_len_1 ; i++)
        array_1[str_1.charAt(i) - 'a'] += 1;
        for (int i = 0 ; i < str_len_2 ; i++)
        array_2[str_2.charAt(i) - 'a'] += 1;
        for (int i = 0 ; i < 26 ; i++){
            if (array_1[i] != 0 && array_2[i] != 0){
                for (int j = 0 ; j < Math.min(array_1[i], array_2[i]) ; j++)
                System.out.print(((char)(i + 'a')));
            }
        }
    }
    public static void main(String[] args) throws IOException{
        String my_str_1 = "itsasample";
        String my_str_2 = "thisisasample";
        System.out.println("The common characters between the two strings in alphabetical order is :");
        common_chars(my_str_1, my_str_2);
    }
}

出力結果

The common characters between the two strings in alphabetical order is :
aaeilmpsst

コードの解説

Demoというクラスの中に、common_charsというメソッドが定義されています。このメソッドでは、サイズ26の整数型配列を2つ宣言しています。これは、英小文字がaからzまでの26種類であることに対応しており、各文字列の長さはそれぞれ別の変数に格納されます。

まず、1つ目のforループでstr_1の各文字を走査し、その文字のASCII値から「a」のASCII値を引いた値をインデックスとして、array_1の該当要素を1ずつ加算していきます。同様に、2つ目のforループでもstr_2に対して同じ処理を行い、array_2に各文字の出現回数を記録します。

続いて、0から25までの各インデックスについて、両方の配列の値が0以外かどうか(= 両方の文字列にその文字が含まれているか)を判定します。条件を満たす場合は、Math.min()メソッドで2つの出現回数のうち小さい方の回数だけ、該当する文字をコンソールに出力します。これにより、複数回登場する共通文字も正しく反映されます。

配列をインデックス0から25の順に走査しているため、出力結果は自動的にアルファベット順になります。mainメソッドでは、比較対象となる2つの文字列「itsasample」と「thisisasample」を定義し、それらを引数としてcommon_charsメソッドを呼び出しています。

計算量について

このアルゴリズムの時間計算量はO(n + m)です(n、mはそれぞれの文字列の長さ)。文字ごとの出現回数を一度の走査で集計できるため、文字列同士を総当たり的に比較する方法よりも効率的です。