文字列49

49. 文字列のアナグラムグループ化

問題記述

文字列の配列が与えられるので、アナグラムを同じグループにまとめなさい。結果のリストは任意の順序で返して構いません。

アナグラムとは、元の単語のすべての文字を並び替えて作られる新しい単語のことです。

例1:

入力: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
出力: [["bat"],["nat","tan"],["ate","eat","tea"]]

例2:

入力: strs = [""]
出力: [[""]]

例3:

入力: strs = ["a"]
出力: [["a"]]

制約：

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] は小文字アルファベットのみを含む

前提知識 - Map

Map はインターフェース

• Map<K, V> は Java のインターフェースであり、キーと値のペアを扱うためのメソッド（例：put(), get(), containsKey()）を定義します。
• このインターフェースは直接インスタンス化できません。代わりに、その実装クラス（例えば HashMap, TreeMap, LinkedHashMap）を使用します。

Javaにおける3つの主な Map 実装クラス

1. HashMap

• 内部構造：ハッシュテーブル（配列＋連結リスト＋赤黒木、JDK 1.8以降）
• 順序：順序なし
• null 許容：1つの null キー、複数の null 値を許可
• スレッドセーフ：非スレッドセーフ
• パフォーマンス：平均的に O(1) の時間計算量

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);

2. TreeMap

• 内部構造：赤黒木（自己平衡二分探索木）
• 順序：キーの自然順序またはカスタム比較器によるソート
• null 許容：null キーは許可されず、例外が発生する
• スレッドセーフ：非スレッドセーフ
• パフォーマンス：O(log n) の時間計算量

Map<String, Integer> map = new TreeMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3); // キーのアルファベット順で並ぶ

3. LinkedHashMap

• 内部構造：ハッシュテーブル＋双方向リスト
• 順序：挿入順序を維持
• null 許容：1つの null キー、複数の null 値を許可
• スレッドセーフ：非スレッドセーフ
• パフォーマンス：HashMap に近い性能、挿入は若干遅い

Map<String, Integer> map = new LinkedHashMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3); // 挿入順序を保持

比較表

どのクラスを使うか

• HashMap：高速アクセスが必要で、順序を気にしない場合
• TreeMap：キーの順序付き処理が必要な場合（ランキングや範囲検索など）
• LinkedHashMap：挿入順またはアクセス順を保持したい場合（LRUキャッシュなど）

サンプルコード

import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
    public static void main(String[] args) {
        // HashMapの作成
        HashMap<String, Integer> map = new HashMap<>();

        // 要素の追加
        map.put("key1", 1);
        map.put("key2", 2);
        map.put("key3", 3);

        // 要素の取得
        int value = map.get("key1");
        System.out.println("Value for key1: " + value);

        // キーの存在確認
        boolean containsKey = map.containsKey("key2");
        System.out.println("Contains key2: " + containsKey);

        // 値の存在確認
        boolean containsValue = map.containsValue(3);
        System.out.println("Contains value 3: " + containsValue);

        // ループ処理
        for (String key : map.keySet()) {
            System.out.println("Key: " + key + ", Value: " + map.get(key));
        }

        // 要素の削除
        int removedValue = map.remove("key3");
        System.out.println("Removed value: " + removedValue);

        // サイズの取得
        int size = map.size();
        System.out.println("Size of map: " + size);

        // 全要素のクリア
        map.clear();
        System.out.println("Map is empty: " + map.isEmpty());
    }
}

問題の解法

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> anagramMap = new HashMap<>();
        
        for (String word : strs) {
            // 文字列を文字配列に変換し、ソートして共通キーを作成
            char[] charArray = word.toCharArray();
            Arrays.sort(charArray);
            String sortedKey = new String(charArray);
            
            // キーが存在しなければ新しいリストを作成
            anagramMap.putIfAbsent(sortedKey, new ArrayList<>());
            // ソートされたキーに対応するリストに元の文字列を追加
            anagramMap.get(sortedKey).add(word);
        }
        
        // マップの値（グループ）をリストとして返す
        return new ArrayList<>(anagramMap.values());
    }
}