アナグラムかどうかをハッシュで判定する

配列とハッシュ問題 05

2 つの文字列が、文字を並べ替えるだけで同じにできるかを調べる。並べ替えて比べる書き方と、文字の数を数える書き方を比べる練習です。

海外で定番の問題リスト 4 本のうち 4 本に入っています (Blind 75、NeetCode 150、Grind 75、LeetCode Top Interview 150)

問題

英小文字だけでできた 2 つの文字列 a と b を受け取ります。a の文字の順を並べ替えて b と同じにできるなら true、できないなら false を返す関数を書いてください。

文字を足したり消したりはできません。並べ替えるだけです
同じ文字が何回出るかも、ぴったりそろっている必要があります
a と b の長さは、どちらも 0 以上 10000 以下です

入力と出力の例

例 1

a = "below" b = "elbow"

true

例 2

使っている文字の種類は同じでも、数が違えば並べ替えて同じにはできません。

a = "aab" b = "abb"

false

例 3

長さが違えば、それだけで答えは決まります。

a = "note" b = "notes"

false

面接での聞かれ方

面接では、例を添えて短く渡されることが多いです。

「2 つの単語が、文字の並べ替えで同じになるかを判定してください」
書き終えたあとに「いまの書き方の計算量は？」「並べ替えずにできますか？」と続けて聞かれます
「大文字や空白が入ったら？」「日本語なら？」と、入力が広がったときの話を聞かれることもあります

使う文字が英小文字だけなのか、大文字と小文字を同じに見るのかを、最初に確かめておきます。文字の種類が決まると、数え方も選びやすくなります。

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

アルゴリズムのチートシートの「ハッシュマップ」に、この型の要点を表とコードでまとめています。

ハッシュは、値から番地を計算して、探す手間をほぼ 1 回にする仕組みです。重複や回数の問題は、この形で解けます。

まず考える手順

段 1

まずは素直に、両方の文字を並べ替えてから比べます。並べ替えて同じにできる 2 つなら、どちらも文字を順に並べると同じ文字列になります。Python なら sorted(a) == sorted(b) で書けます。

段 2

並べ替えは、長さを n とすると O(n log n) の時間がかかります。けれど、ほしいのは順ではなく「どの文字が何回出たか」だけです。並べ替えずに、文字ごとの回数を数えて比べれば足ります。

段 3

辞書 (Python の dict、JavaScript の Map、Go の map) に、a の文字の回数を数えて入れます。次に b を読みながら、その文字の回数を 1 つずつ減らします。減らす前に 0 になっていたら、b の方が多いので false です。先に長さを比べておけば、最後まで読み切れたときは回数がちょうど打ち消し合っています。

解答

Python

def same_letters(a, b):
    if len(a) != len(b):
        return False
    count = {}
    for ch in a:
        seen = count.get(ch, 0)
        count[ch] = seen + 1
    for ch in b:
        have = count.get(ch, 0)
        if have == 0:
            return False
        count[ch] = have - 1
    return True

JavaScript

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

Go

func sameLetters(
	a, b string,
) bool {
	if len(a) != len(b) {
		return false
	}
	count := map[rune]int{}
	for _, ch := range a {
		count[ch]++
	}
	for _, ch := range b {
		if count[ch] == 0 {
			return false
		}
		count[ch]--
	}
	return true
}

段 1 の並べ替える書き方なら、Python は sorted(a) == sorted(b) の 1 行です。短く書けるので、面接ではまずこちらを言い、そのあとで数える書き方に進むと流れが伝わります。

計算量

時間は O(n) です。a と b を 1 回ずつ読み、辞書を調べるのも書き換えるのも、平均して一定の手間で済みます
使う記憶は、文字の種類の数だけです。英小文字なら多くても 26 種類なので、O(1) と見なせます
段 1 の並べ替える書き方は、時間が O(n log n) で、並べ替えた写しのために記憶を O(n) 使います

よくある間違い

文字の種類だけを比べる。集合 (set) にして比べると、例 2 の aab と abb がどちらも a と b になり、true と答えてしまいます。回数まで比べます
長さを先に比べない。長さを比べずに b だけ読んで減らすと、a に余った文字があっても true を返します。例 3 なら、長さの違いを先に見れば迷いません
JavaScript で文字列をそのまま並べ替えようとする。 文字列には sort が無いので、[...a].sort().join("") のように、いったん並びにしてから並べ替えます

解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.2確認日 2026年10月24日

def same_letters(a: str, b: str) -> bool: """ Goal: 何を返すか idea1: まず思いつく案 -> runtime: O(?) space: O(?) idea2: もっと速い案 -> runtime: O(?) space: O(?) edge case: 空、1 つだけ、など """ # ここに書きます pass # 「実行」を押すと、この行の結果が出ます print(same_letters("below", "elbow"))