【Java】ransomNote と magazine の問題を2パターンで比較してみた（LeetCode #383 Ransom Note )

問題概要

LeetCode 383「Ransom Note」では、次のような問題が出されます。

文字列 ransomNote が、文字列 magazine に含まれる文字だけで構成できるかを判定せよ。
文字は magazine 内で1度しか使えない。

解法①：HashMapを使う方法パターン1

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Character, Integer>map = new HashMap<>();
        for (char c : ransomNote.toCharArray()){
            map.put(c, map.getOrDefault(c, 0)+1);
        }

        for (char c : magazine.toCharArray()){
            if(map.get(c) != null){
                int n = map.get(c)-1;
                map.put(c, n);
            }
        }

        for (int num : map.values()){
            if(num > 0){
                return false;
            }
        }

        return true;
    }
}

HashMap を使って文字とその出現回数を管理。
'a'〜'z' 以外の文字（例：大文字）も扱える。
ただし、毎回hash計算が走るためやや遅め。、ループが多く計算量が高くなる。

Mapは以下のことを内部で行うため、計算量が高くなる

①ハッシュ値 を計算（例：97 → ハッシュ関数 → 97）
②バケット配列のどこに入れるか決める（例：index = hash % 16）
③バケットにリストやツリー構造があるか確認
③もし複数要素があれば、キー同士を equals() 比較
④見つかったら値を返す or 更新する
⑤データが増えるときは リサイズ（再ハッシュ） も発生

解法②：HashMapを使う方法パターン2

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Character, Integer> map = new HashMap<>();

        // magazineの文字をカウント
        for (char c : magazine.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        // ransomNoteの文字を消費
        for (char c : ransomNote.toCharArray()) {
            if (!map.containsKey(c) || map.get(c) == 0) {
                return false;
            }
            map.put(c, map.get(c) - 1);
        }

        return true;
    }
}

HashMap を使って文字とその出現回数を管理。
'a'〜'z' 以外の文字（例：大文字）も扱える。
ただし、毎回hash計算が走るためやや遅めだが、ループ数を減らしたことで計算量が若干低くなる

解法③：配列を使う方法（高速・省メモリ）

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int [] array = new int [26];
        for (char c : magazine.toCharArray()){
            int n = array[c-'a'];
            array[c-'a'] = n + 1;
        }

        for (char c : ransomNote.toCharArray()){
            int n = array[c-'a'];

            if((n-1) < 0){
                return false;

            } 
            array[c-'a'] = n-1;

        }

        return true;
    }
}

'a'〜'z' の26文字を固定配列で管理。
array[c-'a'] = n-1;でnが０より小さくなった後にさらに要求されたときにfalseを返す。
配列の0〜25番目に直接アクセスするため、Mapより計算量が大きく下がる

まとめ

HashMap と配列、どちらの実装も正しい。
ただし、制約が明確（英小文字限定などパターンが決まっている場合）な問題では配列の方が圧倒的に高速。