Guppi StudioPROBLEM 02
文字を並べ替えて同じになる語をまとめる
文字の構成が同じ語をグループ化します。
検索候補の単語を、文字の並べ替えだけで互いに変換できるグループへ整理します。 グループ同士の順番と、グループ内の語順は問いません。
groupAnagrams(words) はグループの配列を返してください。
英小文字だけを扱います。
例
入力: ["tea", "arc", "eat", "car", "bat", "ate"]
出力: [["tea", "eat", "ate"], ["arc", "car"], ["bat"]]入力: ["", "b", ""]
出力: [["", ""], ["b"]]
理由: 空文字列同士も「同じ構成」のグループになる制約
1 <= words.length <= 10,000- 各語の長さは
0以上100以下 - 各語は英小文字のみ
- 目標: 語同士を総当たりで比較しない解法（総当たりは性能テストで時間切れになります）
対応する問題: LeetCode #49 Group Anagrams
まず素朴に解くと — グループの代表と1つずつ比べる
「新しい語が来たら、既存の各グループの代表とアナグラム判定して、合うところに入れる」という作り方が自然に浮かびます。
function isAnagram(a: string, b: string): boolean {
if (a.length !== b.length) return false;
return [...a].sort().join("") === [...b].sort().join("");
}
function groupAnagrams(words: string[]): string[][] {
const groups: string[][] = [];
for (const word of words) {
const group = groups.find((g) => isAnagram(g[0], word));
if (group) group.push(word);
else groups.push([word]);
}
return groups;
}グループ数はほぼ語数に比例して増えるので、比較回数は O(n²)、1回の比較にも語長ぶんのコストがかかります。
どこが遅いのか
性能テストは 10,000 語です。総当たりだと最悪およそ 5,000万回 のアナグラム判定が走り、そのたびにソートや頻度比較をやり直します。「同じ判定を何度も繰り返している」のが遅さの正体です。
発想の転換
語同士を比べるのをやめて、「同じ構成なら同じ文字列になる代表形」を作る。
アナグラムかどうかは並び順を無視した文字の構成だけで決まります。文字をソートして連結すれば、tea も eat も ate も同じ aet になる — この**正規形（canonical key）**を Map のキーにすれば、比較そのものが不要になり、各語は自分のグループへ O(1) で直行できます。
「比較を繰り返す代わりに、同じものが同じキーへ写る変換を設計する」のは、HashMap カテゴリ全体で使い回せる考え方です。
解答例 — 正規形をキーにする
function groupAnagrams(words: string[]): string[][] {
const groups = new Map<string, string[]>();
for (const word of words) {
const key = [...word].sort().join("");
const group = groups.get(key) ?? [];
group.push(word);
groups.set(key, group);
}
return [...groups.values()];
}動きを追う — [“tea”, “arc”, “eat”, “car”, “bat”, “ate”]
| word | key（ソート結果） | 処理後の Map |
|---|---|---|
| tea | aet | aet→[tea] |
| arc | acr | aet→[tea], acr→[arc] |
| eat | aet | aet→[tea, eat], acr→[arc] |
| car | acr | aet→[tea, eat], acr→[arc, car] |
| bat | abt | aet→[…], acr→[…], abt→[bat] |
| ate | aet | aet→[tea, eat, ate], acr→[arc, car], abt→[bat] |
最後に Map の値を並べて返せば完成です。
計算量の比較
語数を n、語の最大長を k とします。
| 解法 | 時間 | 追加領域 | n = 10,000, k = 8 での目安 |
|---|---|---|---|
| 総当たり比較 | O(n² × k) | O(nk) | 数億文字の比較 |
| ソートキー | O(n × k log k) | O(nk) | 約24万文字の処理 |
さらに詰めるなら、キーを「a〜z の出現回数26個を連結した文字列」にするとソートが消えて O(nk) になります。k が大きい入力への追加の一手として、面接の follow-up で聞かれることがあります。
面接でどう話すか
「語同士を総当たりで比較すると O(n²k) になるので、比較をなくす方向で考えます。アナグラムは文字の構成が同じ、つまりソートすると同じ文字列になるので、ソート結果をキーにした Map へ振り分ければ O(n k log k) です。もし k が大きいなら、文字の出現回数をキーにして O(nk) まで下げられます。」
「同じものを同じキーに写す」と一言で言えると、パターンを理解していることが伝わります。
STEPWISE HINTS
ヒント
01最初の一手
並び順ではなく、語を構成する文字の集合を表す共通の印を作れないか考えます。
02処理の組み立て
各語の文字をソートした文字列を Map のキーにすると、同じ構成の語が同じ場所に集まります。
03コードの形
Map<string, string[]> を作る。各 word の文字をソートして key とし、対応する配列へ word を追加する。最後に Map の values を返す。
AFTER ACCEPTED
解説
まずは自分の言葉で方針を説明し、コードに落としてみましょう。