アナグラムグルーピング
「仲間かどうか」を総当たりで確かめない
eat, tea, tan, ate, nat, bat を、文字を並べ替えると一致するもの同士でまとめます。eat と tea と ate が 1 組、tan と nat が 1 組、bat は 1 語だけの組です。こういう関係をアナグラムと言います。
素直にやるなら、すべての 2 語の組について「並べ替えたら一致するか」を確かめます。語数の 2 乗に比例するので、1 万語なら 5,000 万回。そのうえ、A と B が仲間で B と C も仲間だと分かったあとに A と C を確かめるのは、完全に無駄な作業です。
比べるのをやめます。代わりに、仲間なら必ず同じになる合言葉を語ごとに 1 回だけ作り、同じ合言葉の語を同じ箱に入れます。
合言葉で箱に配る
配る形そのものは、どんな合言葉でも変わりません。ここでは文字数を合言葉にしてみます。
Python
words = ["fig", "kiwi", "pear", "ant"]
buckets = {}
for w in words:
key = len(w)
if key not in buckets:
buckets[key] = []
buckets[key].append(w)
print(buckets) # {3: ['fig', 'ant'], 4: ['kiwi', 'pear']}語を 1 回ずつしか見ていません。箱が無ければ作り、あればそこへ足すだけです。あとは合言葉の作り方を差し替えれば、好きな基準でまとめられます。
手間が語数に比例するのは、辞書が「この合言葉の箱はどこか」をほぼ一瞬で答えるからです。箱を順に見て回って探すなら、結局は総当たりに戻ってしまいます。1 万語なら、5,000 万回が 1 万回になります。
合言葉に、文字の個数が残っているか
アナグラムの合言葉に求められる条件は 2 つです。同じ文字を同じ個数だけ持つ 2 語が必ず同じ値になることと、構成が違う 2 語が必ず違う値になること。
たとえば「使われている文字の集まり」を合言葉にすると、後者で失敗します。aab も ab も集まりにすれば a と b なので、同じ箱に入ってしまいます。個数の情報が消えているからです。文字の並び順に左右されず、しかも個数まで残る形を探してください。
出てきた順を保つ
箱の並びは、その合言葉が最初に登場した順にします。Python の辞書と JavaScript の Map は入れた順を覚えているので、そのままで条件を満たします。Java の HashMap は順を保証しないので LinkedHashMap を使い、Go の map も順を保証しないので、合言葉の登場順を別のスライスに記録しておく必要があります。箱の中身のほうは、語を見つけた順に足していけば自然に入力順のままです。
要件
- ソートした文字列をキーにして hashmap でグループ化する
- グループの並びは入力に最初に登場したキー順を保つ (LinkedHashMap 相当)
- グループ内の文字列も入力順を保つ
入出力例
groupAnagrams(["eat","tea","tan","ate","nat","bat"]) → [["eat","tea","ate"],["tan","nat"],["bat"]]
groupAnagrams(["abc"]) → [["abc"]]
groupAnagrams(["ab","ba"]) → [["ab","ba"]]
groupAnagrams(["ab","cd","ef"]) → [["ab"],["cd"],["ef"]]
groupAnagrams(["aa","aa","ab"]) → [["aa","aa"],["ab"]]ヒント
