辞書で同じ文字でできた語を組に分ける

配列とハッシュ問題 08

文字を並べ替えると同じになる語どうしを、1 つの組にまとめます。語ごとに文字の数を数えた物を辞書の鍵にして、同じ鍵の語を集める練習です。

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

問題

英小文字の語の並び strs を受け取ります。文字を並べ替えると同じ語になるものどうし (使う文字とその数がまったく同じもの) を 1 つの組にまとめ、組の並びを返す関数を書いてください。

返す順は次のとおりに決めます。組の中の語は strs に出てきた順に並べます。組どうしは、その組の語が strs に初めて出てきた順に並べます
同じ語が 2 回あれば、2 つとも同じ組に入れます。空の語 "" も 1 つの語として扱います
strs の長さは 1 以上 10000 以下、語の長さは 0 以上 100 以下で、使う文字は a から z だけです

入力と出力の例

例 1

strs = ["stop", "pots", "melon", "lemon", "tops"]

[["stop", "pots", "tops"], ["melon", "lemon"]]

例 2

使う文字の種類が同じでも、数が違えば別の組です。

strs = ["aab", "abb", "bab", "baa"]

[["aab", "baa"], ["abb", "bab"]]

例 3

空の語どうしも 1 つの組になります。

strs = ["", "b", ""]

[["", ""], ["b"]]

面接での聞かれ方

面接では、例を 1 つ見せて、短く聞かれることが多いです。

「文字を入れ替えると同じになる単語どうしをグループにしてください」
「2 つの語が同じ組かを、どうやって調べますか？」と、比べ方を先に聞かれます
書き終えたあとに「1 語の長さが長いとき、もっと速くできますか？」と、鍵の作り方を詰められます
「大文字や記号が混ざったら？」と、文字の種類を広げた場合を聞かれることもあります

返す順をどうするかは、問題文に無ければ先に確かめます。ここでは、出てきた順を保つと決めてあります。

ヒント

まだ開いていません

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

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

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

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

まず考える手順

段 1

まずは素直に、語を 1 つずつ見て、今ある組の先頭の語と同じ文字でできているかを比べる書き方を考えます。正しく動きますが、組の数だけ比べるので、組が多いと 2 重の繰り返しに近い手間になります。

段 2

同じ組の語には、共通の「名札」を付けられることに目を向けます。たとえば、語の文字を小さい順に並べ替えた物は、同じ組ならどれも同じになります。stop も pots も opst です。この名札を辞書の鍵にして、同じ鍵の語を 1 つの並びに集めれば、比べる手間が要りません。

段 3

並べ替えた名札は、語の長さを k とすると作るのに O(k log k) かかります。使う文字は a から z の 26 種類だけなので、文字ごとの数を数えた 26 個の数の並びも名札になります。数えるのは O(k) で済みます。この並びを、辞書の鍵にできる形 (Python はタプル、JavaScript は文字列、Go は長さ 26 の配列) に直して使います。

段 4

返す順を守ります。辞書に初めての鍵が出てきたときに組を作り、そのあとの語は出てきた順に後ろへ足していけば、組の中は元の順、組どうしは最初に出た順になります。Python の dict と JavaScript の Map は足した順を覚えていますが、Go の map は順を覚えないので、組の並びを別に持ち、辞書には組の番号を入れます。

解答

Python

def group_anagrams(strs):
    groups = {}
    for s in strs:
        count = [0] * 26
        for ch in s:
            i = ord(ch) - 97
            count[i] += 1
        key = tuple(count)
        if key not in groups:
            groups[key] = []
        groups[key].append(s)
    return list(groups.values())

JavaScript

function groupAnagrams(strs) {
  const groups = new Map();
  for (const s of strs) {
    const count = Array(26)
      .fill(0);
    for (const ch of s) {
      const code =
        ch.charCodeAt(0);
      count[code - 97]++;
    }
    const key = count.join(",");
    if (!groups.has(key)) {
      groups.set(key, []);
    }
    groups.get(key).push(s);
  }
  return [...groups.values()];
}

Go

func groupAnagrams(
	strs []string,
) [][]string {
	index := map[[26]int]int{}
	out := [][]string{}
	for _, s := range strs {
		var key [26]int
		for _, ch := range s {
			key[ch-'a']++
		}
		i, ok := index[key]
		if !ok {
			i = len(out)
			index[key] = i
			out = append(out, nil)
		}
		out[i] = append(out[i], s)
	}
	return out
}

97 は a の文字の番号です。JavaScript の鍵を count.join(",") と区切り付きでつなぐのは、数が 2 桁になったとき、区切りが無いと 1 と 11 の続きが見分けられなくなるからです。

計算量

時間は O(n k) です。n は語の数、k は語の長さのいちばん大きい値です。語ごとに文字を 1 回なめて数え、26 個の数から鍵を作り、辞書を調べます
使う記憶は O(n k) です。全部の語を組に入れて返し、鍵も語の数だけ覚えます
段 2 の並べ替えた名札を使う書き方は、時間が O(n k log k) です。語が短ければ差は小さいので、面接ではどちらでも通りますが、違いを言えると強みになります

よくある間違い

鍵に Python のリストを使う。 リストは中身を変えられるので辞書の鍵になれず、エラーになります。tuple(count) に直します。JavaScript で並びをそのまま Map の鍵にすると、中身が同じでも別の物として扱われ、組がまとまりません
文字の種類だけで比べる。集合で比べると、例 2 の aab と abb が同じ組になってしまいます。文字ごとの数まで比べます
数をつなぐときに区切りを入れない。 a が 1 個で b が 11 個の語と、a が 11 個で b が 1 個の語が、同じ鍵になることがあります
Go で map を回して組を返す。 map を回す順は毎回変わるので、組の順が決まりません。組の並びを別に持ちます

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

def group_anagrams(strs: list[str]) -> list[list[str]]: """ Goal: 何を返すか idea1: まず思いつく案 -> runtime: O(?) space: O(?) idea2: もっと速い案 -> runtime: O(?) space: O(?) edge case: 空、1 つだけ、など """ # ここに書きます pass # 「実行」を押すと、この行の結果が出ます print(group_anagrams(["stop", "pots", "melon", "lemon", "tops"]))