Group Anagrams
単語のリスト strs が与えられます。一方の単語の文字を並べ替えたものがもう一方の単語であり、それぞれの文字が同じ回数使われているとき、2つの単語はアナグラムです。すべての単語をそれぞれのアナグラムとグループ化し、各グループにつき1つの文字列を返してください。グループ内の単語をアルファベット順に並べ、半角スペース1つでつなげます。グループは、それぞれの先頭の単語のアルファベット順に並べます。
同じ単語が複数ある場合は、そのグループ内に重複して含めます。アナグラムがない単語は、1語だけのグループになります。アルファベット順とは辞書順のことです。aab は ab より前に、ab は abc より前に来ます。
関数
- strsstring-array
- グループ化する単語（小文字のみ）
- 戻り値string-array
- 各グループにつき1つの文字列：その単語を並べ替えてスペースで結合し、グループは最初の単語順に並べる
制約
1 ≤ strs.length ≤ 40001 ≤ strs[i].length ≤ 8- すべての単語は小文字の英字のみで構成されています。
例
- 入力
- strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]
- 出力
- ["apple", "enlist listen silent", "notes onset stone tones"]
- 説明
enlist、listen、silentは、それぞれe、i、l、n、s、tを1回ずつ使います。notes、onset、stone、tonesはe、n、o、s、tを共有しています。appleは何にも一致せず、最初の単語なので先頭になります。
- 入力
- strs = ["race", "arc", "care", "car", "acre"]
- 出力
- ["acre care race", "arc car"]
- 説明
acre、care、raceには a、c、e、r が含まれています。arcとcarには e がないため、それらは独自のグループを形成します。2文字目では c が r より前に来るため、acreはarcより前に来ます。
- 入力
- strs = ["b", "a", "b"]
- 出力
- ["a", "b b"]
- 説明
bの2つのコピーは互いにアナグラムであり、どちらもグループに残ります。aには対応するものがなく、先頭に来ます。
発展問題
単語に任意のUnicode文字を含められる場合、ソートした文字または文字数のどちらのキーが引き続き機能し、何を変更しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
2つの単語がアナグラムであるのは、同じ文字が同じ回数だけ含まれている場合に限ります。他の単語を見ずに、ある単語から計算でき、そのアナグラムすべてで同じ値になるものは何でしょうか？
各単語の文字を並べ替えます。
listenもsilentもeilnstになります。この並べ替えた形がグループの名前となるため、これをキー、単語のリストを値とするハッシュマップを使えば、1回の走査ですべてのグループを集められます。グループ分けする前に、入力全体を並べ替えます。すると単語がアルファベット順に届くため、各グループのリストはすでに順番どおりになっており、各グループは最初の単語が届いたときに作成されます。各リストをスペースで結合します。
解説
各単語だけからキーを計算します。そのキーはすべてのアナグラムで同じになり、それ以外の単語では異なるものです。単語の文字を並べ替えたものがそのようなキーになります。また、キーからグループへのハッシュマップを使えば、1回の走査でグループをまとめられます。最初に単語をソートすれば、必要な順序も自然に得られます。
各単語をすべてのグループと比較する
正しいが、最大のテストでは終わらない
考え方
グループのリストを保持し、各単語を各グループの最初の単語と比較します。アナグラムであることは推移的なので、グループごとに1回比較すれば所属が決まります。2つの単語は、長さが同じで、26文字それぞれの出現回数も同じならアナグラムです。まず入力を並べ替えます。すると各グループ内の単語はアルファベット順に並び、グループは最初の単語の順に作成されます。
どの単語同士もアナグラムでない場合、各単語はそれ以前のすべてのグループと比較されます。4000語では約8 × 10^6回の比較となり、それぞれで最大8文字と26個のカウンターを調べます。
アルゴリズム
- 単語をアルファベット順に並べます。
- 各単語について、最初の単語の文字数が同じグループを探し、その単語を追加します。一致するグループがなければ、新しいグループを作成します。
- 各グループの単語を1つのスペースでつなぎ、作成した順に返します。
def is_anagram(a, b):
# Same length, and every letter appears as often in a as in b.
if len(a) != len(b):
return False
counts = [0] * 26
for c in a:
counts[ord(c) - 97] += 1
for c in b:
counts[ord(c) - 97] -= 1
return all(x == 0 for x in counts)
def groupAnagrams(strs):
# Sort first: each group fills up in alphabetical order,
# and groups are created in the order of their first word.
groups = []
for word in sorted(strs):
for group in groups:
if is_anagram(group[0], word):
group.append(word)
break
else:
groups.append([word])
return [" ".join(group) for group in groups]ハッシュマップ内で文字をソートしてグループ化する
考え方
単語そのものからグループの名前を計算します。単語の文字を並べ替えると、アナグラムはすべて同じ文字列になります。listen、silent、enlistはすべてeilnstになり、stoneはenostになります。2つの単語が同じ並べ替え後の形になるのは、同じ文字が同じ回数だけ含まれている場合に限られます。これがアナグラムの定義です。キーから単語リストへのハッシュマップを使えば、1回の走査ですべてをグループ化でき、ある単語を別のグループの単語と比較する必要もありません。
順序は、前と同じように入力を先に並べ替えることで決まります。各リストはアルファベット順に並び、グループの最初の単語が到着したときにキーがマップに追加されます。挿入順序を保持するマップなら、その順序でグループを返します。そうでなければ、グループをリストに保持し、各キーをそのインデックスに対応付けます。
入力の並べ替えにかかるコストは、4000個の単語の場合、約5 × 10^4回の単語比較で、8 × 10^6回ではありません。
アルゴリズム
- 単語をアルファベット順に並べます。
- 各単語について、文字を並べ替えてキーを作ります。
- ハッシュマップでキーを検索します。新しいキーの場合は、そのキー用の空のグループを作り、グループは作成した順に保ちます。
- 単語をそのキーのグループに追加します。
- 各グループの単語を半角スペース1つで結合して返します。グループは作成順に並べます。
def groupAnagrams(strs):
# Sort first: each group fills up in alphabetical order,
# and groups are created in the order of their first word.
groups = {} # key (the letters in sorted order) -> the group's words
for word in sorted(strs):
key = "".join(sorted(word))
groups.setdefault(key, []).append(word)
# A dict keeps insertion order, so the groups come out by first word.
return [" ".join(words) for words in groups.values()]
落とし穴と境界ケース
- 最初の単語ではなく、キーでグループを並べ替えている。
["cab", "bad"]の場合、キーabcとabdではcabが先になるが、先に来るべきなのはbad。 - 単語を集合に格納している。
["b", "a", "b"]ではb bになる必要があるが、集合では同じ要素は1つしか保持されない。 - 重複しない文字だけからキーを作っている。
abとaabbは同じ2種類の文字を使っているが、アナグラムではない。 - 各グループ内の単語は並べ替えているが、入力もグループも並べ替えていない。そのため、挿入順は最初の単語ではなく入力に従う。
よくある質問3
Group Anagrams の時間計算量はどれくらいですか？
ソート済み文字キーの構築には、最大 k 文字の単語 n 個に対して O(n · k log k) かかり、マップの処理には O(n · k) かかります。出力を順序付けるために単語をソートすると O(n · k · log n) が加わり、これが支配的です。キーとグループに必要な空間計算量は O(n · k) です。
各単語を並べ替えるより、文字の出現回数をキーにするほうが速いですか？
カウントキー（26文字の出現回数を1#0#2#…のようなテキストで表したもの）は、O(k log k)ではなくO(k)で済むため、長い単語では有利です。8文字以下なら、ソートも同じ速さです。どちらのキーも正確です。2つの単語のカウントが同じなのは、ソートした文字が同じ場合に限ります。
文字コードの合計をキーとして使わないのはなぜですか？
異なる文字でも、合計が同じになることがあります。a + d は b + c に等しいため、ad と bc は同じグループに属します。文字ごとに素数を1つ割り当てて掛け合わせれば正確ですが、z に 101 を使うと、z が10個並ぶ単語は64ビット整数の範囲を超えます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def groupAnagrams(strs):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]
期待される出力
["apple", "enlist listen silent", "notes onset stone tones"]