Group Anagrams
単語のリスト strs が与えられます。一方の単語の文字を並べ替えるともう一方になる場合、その2つの単語はアナグラムです。つまり、同じ文字がそれぞれ同じ回数使われています。すべての単語をアナグラムごとにグループ分けし、各グループにつき1つの文字列を返してください。文字列にはグループ内の単語をアルファベット順に並べ、単一のスペースで区切って含めます。グループは、それぞれの先頭の単語のアルファベット順に並べてください。
同じ単語が2回現れる場合は、そのグループにも2回含めます。アナグラムがない単語は、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はどれにも一致しません。先頭の単語で並べると、グループはapple、enlist、notesの順になります。
- 入力
- 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には相手がいないため、最初に来ます。
提出時に隠しテスト+15件
発展問題
単語に26個の小文字ではなく、任意のUnicode文字が含まれるとします。2つのキーのうち、ソートした文字と文字数のどちらが引き続き機能しますか。また、どのように変更しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
2つの単語がアナグラムであるのは、同じ文字が同じ回数だけ含まれている場合に限ります。他の単語を見ずに1つの単語から計算でき、その単語のすべてのアナグラムで同じ値になるものは何でしょうか？
各単語の文字を並べ替えます。
listenとsilentはどちらもeilnstになります。この並べ替えた形をグループ名として使い、これをキーに単語のリストを格納するハッシュマップを使えば、1回の処理ですべてのグループを集められます。グループ分けする前に、入力全体をソートします。すると単語がアルファベット順に並んで届くため、各グループのリストはすでに順序どおりになっており、各グループは最初の単語が届いたときに作成されます。すべてのリストをスペースでつなげます。
解説
すべての単語をほかのすべての単語と比較する方法でも動作しますが、各ペアにつき比較を1回ずつ行う必要があります。この問題を解決するのは、標準化されたキーです。これは、単語1つだけから計算する値で、そのアナグラム同士では同じになり、それ以外の単語とは異なります。単語の文字を並べ替えたものがそのようなキーになります。キーからグループへのハッシュマップを使えば、グループ分けを1回の走査で行えます。グループ分けの前に単語をソートすれば、必要な順序も自然に得られます。
各単語をすべてのグループと比較する
正しいが、最大のテストでは終わらない
考え方
アナグラムであることは推移的です。つまり、stone が notes と一致し、notes が tones と一致するなら、stone は tones と一致します。そのため、新しい単語はグループのすべての単語と照合する必要はありません。グループの最初の単語と比較すれば、そのグループに属するかどうかを判断できます。
2つの単語を比較するには、文字を数えます。長さが同じで、それぞれの文字が一方ともう一方に同じ回数だけ現れるなら、それらはアナグラムです。最初の単語の各文字について1を加算し、2つ目の単語の各文字について1を減算して、26個すべてのカウンターが最終的に0になることを確認します。
最初に入力をソートすれば、順序は自然に整います。単語はアルファベット順に到着し、それぞれの単語が自分のグループの末尾に加わるため、各グループはソートされた状態を保ちます。各グループはアルファベット順で最初の単語が到着したときに作られるので、グループも最初の単語の順に並んでいます。
問題は走査にかかるコストです。アナグラムの単語が1組もない場合、各単語はそれより前にあるすべてのグループと比較されます。4000個の単語では約4000 × 3999 / 2 ≈ 8 × 10^6回の比較が必要になり、各比較で最大8文字と26個のカウンターを処理します。これは最大規模のテストではPython、Lua、Rにとって遅すぎます。また、処理量はリストのサイズの二乗に比例して増えるため、単語数が10^5個になると、どの言語でも処理しきれません。
アルゴリズム
- 単語をアルファベット順に並べ替えます。
- それぞれ単語のリストであるグループのリストを保持します。
- 各単語について、最初の単語の文字数が同じグループを探し、そのグループに単語を追加します。
- 一致するグループがなければ、この単語だけを含む新しいグループを作成します。
- 各グループの単語を単一のスペースで結合し、作成した順にグループを返します。
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回の走査ですべてをグループ化できます。各単語の処理には、最大8文字を1回並べ替える処理とマップの検索が必要なだけで、ほかのグループと比較することはありません。
順序を保つには、最初の方法と同様に、グループ化する前に入力をソートします。単語はアルファベット順に到着するため、各リストには順番どおりに単語が追加され、グループの最初の単語が到着した時点でキーがマップに追加されます。挿入順を保持するマップ（Python の dict、JavaScript の Map、Java の LinkedHashMap、Dart の map、Ruby のハッシュ、PHP の配列）なら、グループもその順序で返されます。マップに順序がない場合は、各グループのインデックスをマップに保存し、グループ自体はリストに格納します。
入力のソートには、最大k文字の比較が約n log n回必要です。単語が4000個の場合、単語の比較回数は約5 × 10^4回となり、8 × 10^6回より少なくなります。キーの作成にはさらにO(n · k log k)が加わりますが、k ≤ 8なので、その分は比較的小さなコストです。
アルゴリズム
- 単語をアルファベット順に並べ替えます。
- 各単語について、文字を並べ替えてキーを作成します。
- ハッシュマップでキーを検索します。新しいキーの場合は、グループを作成した順序を保ちながら、空のグループを作成します。
- 単語をそのキーのグループに追加します。
- 各グループの単語を単一のスペースで結合し、グループを作成した順序で返します。
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種類の文字を使いますが、aabbにはそれぞれの文字が2つずつあるため、アナグラムではありません。 - 文字コードを合計してキーを作る。
adとbcの合計は同じなので、文字を1つも共有しない単語が同じグループにまとめられてしまいます。 - 各グループは並べ替えるが、入力は並べ替えず、その後グループの並べ替えを忘れる。すると挿入順は最初の単語の順序ではなく、入力の順序になります。
- 手作業で結合し、グループの文字列の先頭または末尾にスペースを残す。
よくある質問4
アナグラムのグループ化の時間計算量はどれくらいですか？
文字をソートしたものをキーとするハッシュマップでは、最大 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問解くとパターンが身につきます。
Python
def groupAnagrams(strs):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]
期待値
["apple", "enlist listen silent", "notes onset stone tones"]