アナグラム判定｜コードで実践

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

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

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

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

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

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

アナグラム判定

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

ソート方式 は sorted(a) == sorted(b) で 1 行ですが、ソートのコストで O(n log n) になります

第 4 章の coding 仕上げは アナグラム判定 です

図のポイント (テキスト併記)

アナグラム判定とは

2 つの文字列が同じ文字の並び替えになっているか (アナグラム) を、map による文字数カウントで判定する。

第 4 章の coding 仕上げは アナグラム判定 です。アナグラム (anagram) とは「同じ文字を並び替えてできる単語のペア」のことです。たとえば listen と silent はアナグラムですし、evil と vile もアナグラムです。日本語だと「ひらがなや漢字の並び替え」をイメージするとよいでしょう。

本レッスンでは、2 つの文字列 a と b を受け取り、a と b が アナグラムになっているか を boolean で返します。実装には 2 つの代表的なアプローチがあります。map で文字数を数えるパターンと、ソート してから一致を見るパターンです。本問では map 方式 を採用し、第 4 章の総まとめとして頻度集計の応用を体験します。

アナグラム判定は『2 つの文字列の文字数分布が同じか』を判定する問題。map による頻度集計の良い演習。

2 つのアプローチ

diagram (will load when visible)

図のポイント (テキスト併記)

ソート方式 は sorted(a) == sorted(b) で 1 行ですが、ソートのコストで O(n log n) になります

ソート方式 は sorted(a) == sorted(b) で 1 行ですが、ソートのコストで O(n log n) になります。コードは短いですが速度は劣ります。

map 方式 は、a の各文字を +1、b の各文字を -1 して、最後にすべてのカウントが 0 なら同じ分布、と判定します。O(n) で完了し、map のキー数も最大 26 (英小文字なら) や Unicode の文字種数で抑えられます。

仕様

2 つの文字列 a と b を受け取り、アナグラムなら true、そうでないなら false を返す
大文字小文字は区別する ('a' と 'A' は別の文字)
空文字同士はアナグラム (true)
長さが違うなら即 false

Python での実装

Python

def isAnagram(a, b):
    if len(a) != len(b):
        return False
    counts = {}
    for ch in a:
        counts[ch] = counts.get(ch, 0) + 1
    for ch in b:
        counts[ch] = counts.get(ch, 0) - 1
        if counts[ch] < 0:
            return False
    return True

a で +1、b で -1。途中で -1 になったら、b にだけある文字が出現したということなので その時点で False。最後まで -1 にならなければ、長さが同じだったので必然的に全カウントが 0 になり、True です。

JavaScript での実装

JavaScript

function isAnagram(a, b) {
  if (a.length !== b.length) return false;
  const counts = new Map();
  for (const ch of a) {
    counts.set(ch, (counts.get(ch) || 0) + 1);
  }
  for (const ch of b) {
    const c = (counts.get(ch) || 0) - 1;
    if (c < 0) return false;
    counts.set(ch, c);
  }
  return true;
}

ロジックは Python と完全に同じです。Map を使うと整数キーやオブジェクトキーも扱えますが、文字列キーなら Object でも問題ありません。

map 方式は途中打ち切りができる点でも優秀。差分がマイナスになった瞬間に false で抜けられる。

Java / Go での実装

Java

import java.util.*;
public class Solution {
    public static boolean isAnagram(String a, String b) {
        if (a.length() != b.length()) return false;
        Map<Character, Integer> counts = new HashMap<>();
        for (char ch : a.toCharArray()) {
            counts.put(ch, counts.getOrDefault(ch, 0) + 1);
        }
        for (char ch : b.toCharArray()) {
            int c = counts.getOrDefault(ch, 0) - 1;
            if (c < 0) return false;
            counts.put(ch, c);
        }
        return true;
    }
}

Java は char を Map<Character, Integer> のキーに使います。toCharArray() で文字配列に変換すると for-each ループが書きやすくなります。

計算量

文字列の長さを n とすると、a の走査と b の走査が各 O(n)、map の操作は平均 O(1)。合計 O(n) です。ソート方式の O(n log n) と比較すると、長い文字列ほど map 方式が有利になります。空間計算量は O(k) (k は文字種数)。英小文字限定なら k <= 26 で、実質定数。

長さチェックを最初に行うことで、不要な集計を回避できる。たいていの集合系問題では『サイズが違うなら即 false』の前置きが効く。

よくある間違い

1 つ目は 長さチェック忘れ です。長さが違う文字列は絶対にアナグラムになり得ないので、最初に len(a) != len(b) で弾くと無駄な集計が省けます。

2 つ目は 大文字小文字の扱い を仕様で決めていないケース。本問では区別する仕様ですが、業務だと lower() で正規化してから比較したいこともあります。事前に揃えるかどうかは要件次第。

3 つ目は map に未登録のキーへの加算 で例外を出す書き方です。counts[ch] = counts.get(ch, 0) + 1 のように、get(key, 0) で初期値を補う癖をつけましょう。

やってみよう

'listen' と 'silent' で結果が true になることを手で追う。
'aabb' と 'abab' も true。それぞれの文字数分布が {'a':2, 'b':2} で一致するから。
ソート方式で同じ判定を書き、O(n log n) と O(n) の差を体感する。
「2 つの文字列で 共通する文字種 を返す関数」も、map を使えば自然に書ける。応用問題として書いてみる。

第 4 章のおさらい — 第 4 章では スタック / キュー / set / map という 4 つの基本データ構造に触れました。どれも 平均 O(1) の操作を提供し、素朴な配列実装の O(n^2) を O(n) に落とす強力な道具です。「どのデータ構造が向くか」を選べる引き出し を増やすことが、CS の学習で最も実戦に効く力になります。

よくある質問

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 セクションを読み返してみましょう。

関連レッスン

アナグラム判定

アナグラム判定

2 つのアプローチ

仕様

Python での実装

JavaScript での実装

Java / Go での実装

計算量

よくある間違い

やってみよう

よくある質問

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

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

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

次のレッスン

要件

入出力例

ヒント

メモ