アナグラムグルーピング｜コードで実践

アナグラムグルーピング

このレッスンで分かること

全体としては O(n * k * log k) で、これがソートを使うときの定番計算量です

アナグラム とは、ある単語の文字を並び替えて作った別の単語のことです

本問では、文字列の配列を受け取り、互いにアナグラムであるもの同士を グループ化 して返します

アナグラムグルーピングとは

文字列の配列を、同じ文字の並び替えになっているもの同士でグループ化する。ソートをキーにした hashmap 分類の典型問題。

アナグラム とは、ある単語の文字を並び替えて作った別の単語のことです。例えば "eat"、"tea"、"ate" は互いにアナグラム。"tan" と "nat" もアナグラム。一方で "bat" は他のどれとも違う文字構成です。

本問では、文字列の配列を受け取り、互いにアナグラムであるもの同士を グループ化 して返します。出力は「2 次元配列」のような形になります。具体的な並び順は問わず、グループの中身が揃っていれば OK というのが一般的な仕様です。

アナグラム判定は「文字の構成 (multiset) が同じか」を見る。hashmap のキーに使える正規化を見つけられるかが鍵。

グループ化の発想

アナグラム判定の鉄板は「文字の構成を同じキーに正規化する」ことです。

ソート: "eat"、"tea"、"ate" を 文字単位でソート するとすべて "aet"。これをキーにできる。
文字数のタプル: (e=1, a=1, t=1) のようなタプル。これも全部同じになる。

本レッスンでは、シンプルで多言語間でも書きやすい 「文字ソート」 方式を使います。

diagram (will load when visible)

Python の実装

Python

def groupAnagrams(arr):
    buckets = {}
    for s in arr:
        key = "".join(sorted(s))
        if key not in buckets:
            buckets[key] = []
        buckets[key].append(s)
    # 各グループは入力順を保持
    # キーの出現順でグループを並べる (Python 3.7+ の dict は挿入順を保つ)
    return list(buckets.values())

ポイントは "".join(sorted(s)) でソート済み文字列をキーにすること。Python の sorted() は文字列を渡すと 文字の配列 を返すので、"".join() で再結合します。

JavaScript の実装

JavaScript

function groupAnagrams(arr) {
  const buckets = new Map();
  for (const s of arr) {
    const key = s.split("").sort().join("");
    if (!buckets.has(key)) buckets.set(key, []);
    buckets.get(key).push(s);
  }
  return Array.from(buckets.values());
}

Map を使えば、Python の dict と同じく 挿入順 が保たれます。出力順がテストで重要な場合に役立ちます。

計算量の分析

配列の長さを n、各文字列の最大長を k とすると、

各文字列のソート: O(k log k)
それを n 個処理: 合計 O(n * k * log k)
hashmap への追加・取得: O(k) 程度 (キー比較)

全体としては O(n * k * log k) で、これがソートを使うときの定番計算量です。さらに高速化したいなら、26 文字のカウント配列をキーにして O(n * k) まで落とせます。

「同じものを集める」問題は hashmap で キーの正規化 ができれば一発で解ける。発想は集合論の同値類と同じ。

出力順について

テストでは出力配列の中身を比較するときに 集合として比較 することが多いですが、本問では Python / JS / Java / Go すべてで挿入順を保つ実装を使い、結果として 入力に最初に出てきたアナグラムグループから順に並ぶ ことを期待しています。Python の dict と JS の Map はそのまま挿入順を保ちます。Java は LinkedHashMap を、Go は map とは別にキーの登場順を記録するスライスを併用することで、同じ並び順を実現します。同じグループ内でも、入力に現れた順を保ちます。

よくある間違い

1 つ目は キーの正規化を間違えるケース です。set(s) をキーにすると "aab" と "ab" が同じグループに入ってしまいます。multiset (文字数も含む) を正規化する必要があります。

2 つ目は 言語ごとの hashmap のキー制約 です。Python の dict や JS の Map は文字列キーで問題ありませんが、Java では挿入順を保証する LinkedHashMap<String, List<String>> を使います（HashMap では挿入順が保証されず、出力順の要件を満たせません）。Go では文字列がキーになる map[string][]string を使いますが、map 自体は挿入順を保証しないため、別途キーの登場順を記録するスライスを管理する必要があります。

3 つ目は 大文字小文字 を区別すべきか曖昧なケースです。本問では「英小文字のみ」と仮定するので問題ありませんが、現実の問題では先に s.lower() を入れることが多いです。

やってみよう

["eat", "tea", "tan", "ate", "nat", "bat"] を入力して、3 つのグループ [[eat, tea, ate], [tan, nat], [bat]] が返るか確認する。
26 文字カウント配列をキーにする版を書いてみる。文字列の最大長が大きいときに効く。
同じパターンで「同じ長さ の文字列をグループ化」する関数も書いてみる。キーを len(s) にするだけ。

ハッシュマップでのグルーピングは、データ集計・カウント・分類の万能ツール。慣れるとアルゴリズムの世界が一気に広がる。

よくある質問

Q. 回文判定の最も簡潔な方法は？

A. Python なら s == s[::-1] の 1 行が最短です。Java/JS は両端からポインタを動かして突き合わせます。大文字小文字・空白・記号を無視するなら、事前に正規化（toLowerCase、replace）してから比較するのが定石です。

Q. アナグラム判定の最速アルゴリズムは？

A. 文字数のカウント配列（英小文字なら 26 個の int 配列）で比較するのが O(n) で最速です。ソート（O(n log n)）よりも僅かに速く、文字種が少ないときに有効です。Unicode 全般を扱うなら HashMap で頻度集計してください。

Q. 応用問題にはどんなものがありますか？

A. 最長回文部分文字列（Manacher 法で O(n)）、回文の数え上げ、グループアナグラム判定などが定番です。LeetCode の Top 100 にも複数含まれており、面接でも頻出のテーマです。

次のレッスン

次は 第4章まとめクイズ — 配列 / 文字列の応用 で、文字列の配列を、同じ文字の並び替えになっているもの同士でグループ化するを学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

アナグラム分類の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. アナグラム分類とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

アナグラムグルーピング