【Java】文字列のユニーク性を判定するアルゴリズムの実装方法

はじめに

Javaで文字列を扱う際、ある文字列が重複する文字を含んでいるかどうかを判定したい場合があります。
この記事では、文字列が全てユニークであるかどうかを判定するアルゴリズムを学習したのでアウトプットしました。

例題

trueの場合
value = ABC123

falseの場合
value = AABBCC

アルゴリズムの概要

アルゴリズムは以下の手順で実装されます。

• ASCII文字の範囲(0から127)の要素数を持つ配列 count を作成します。初期値はすべて0とします。
• 入力された文字列の各文字を順番に取り出し、その文字のASCIIコードをインデックスとして count 配列の要素をインクリメントします。
• count 配列の要素が1より大きい場合、重複する文字が存在するため、文字列はユニークではありません。その場合は false を返します。
• 全ての文字について処理が終了したら、重複する文字が存在しないため、文字列はユニークです。その場合は true を返します。

実装したコード

文字列に重複文字が無いか比較

public class UniqueStringChecker {

    public static boolean isUniqueChars(String str) {
        if (str.length() > 128) {
            // ASCII文字は全部で128種類なので
            // それ以上の文字が存在する場合どこかに重複した文字があるということになります
            return false;
        }

        int[] count = new int[128];
        // int型の配列を用意することで数字のみが入る配列を用意します
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
        // charAt()メソッドは指定した文字列を1文字取得します
            count[ch]++;
        // int型で指定した配列にインクリメントすることで
        // カウントを1増やします
        // count[a]の場合、aという文字が1文字あるという構図になります
            if (count[ch] > 1) {
        // 繰り返し処理でcountの配列が1以上のものが見つかった場合、
        // 重複が見つかったとしてfalseを返します
                return false;
            }
        }

        //　上記の条件に当てはまらなかった場合、重複なしとしてtrueを返します
        return true;
    }

    public static void main(String[] args) {
        String input = "abcdefg";
        boolean isUnique = isUniqueChars(input);
        System.out.println("入力文字列 '" + input + "' はユニークですか？ " + isUnique);
    }
}

実行結果

入力文字列 'abcdefg' はユニークですか？ true

まとめ

この記事では、Javaで文字列のユニーク性を判定するアルゴリズムを実装しました。ASCII文字に限定し、配列を使用することで効率的に処理を行いました。重複する文字が存在しない場合は true を、存在する場合は false を返す仕組みです。