Pythonで文字列をアナグラムごとにグループ化する方法

問題の概要

複数の文字列が与えられたとき、それらをアナグラム（並べ替えると同じ文字になる単語）ごとにグループ化する問題を考えてみましょう。

例えば、入力が ["eat", "tea", "tan", "ate", "nat", "bat"] の場合、出力は次のようなグループになります。

[["ate","eat","tea"],["nat","tan"],["bat"]]

「eat」「tea」「ate」は同じ3文字を含むため同じグループに、「tan」と「nat」も同様にグループ化され、「bat」は対応する単語がないため単独のグループになります。

解決のアプローチ

この問題は、以下の手順で効率的に解くことができます。

• 結果を格納するための辞書（マップ）res を用意します。
• 文字列配列の各要素 i について処理を行います。
  • 文字列 i をソートし、それを結合した文字列をキー x とします。
  • キー x がすでに辞書に存在する場合は、そのリストに i を追加します。
• 存在しない場合は、新しいキーとして result[x] = [i] を作成します。
• 最後に、辞書の値（各グループのリスト）を返します。

この方法のポイントは、アナグラムである文字列はソートすると必ず同じ文字列になるという性質を利用している点です。これにより、各文字列を O(k log k)（k は文字列の長さ）で処理でき、全体の計算量は O(n・k log k) となります。

Pythonでの実装例

実際のコードを見て、理解を深めましょう。

class Solution:
    def groupAnagrams(self, strs):
        result = {}
        for i in strs:
            x = "".join(sorted(i))
            if x in result:
                result[x].append(i)
            else:
                result[x] = [i]
        return list(result.values())

ob1 = Solution()
print(ob1.groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

入力

["eat", "tea", "tan", "ate", "nat", "bat"]

出力

[["ate","eat","tea"],["nat","tan"],["bat"]]

コードの解説

この実装では、sorted(i) によって各文字列を文字単位でソートしたリストを取得し、"".join() で1つの文字列に結合しています。例えば「eat」も「tea」も「ate」も、ソートするとすべて「aet」になるため、同じキーとして扱われます。

さらに、Pythonでは collections.defaultdict(list) を使うと、キーの存在チェックを省略してより簡潔に書くこともできます。

from collections import defaultdict

def groupAnagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        groups["".join(sorted(s))].append(s)
    return list(groups.values())

どちらの実装でも、与えられた文字列リストをアナグラムごとに正しくグループ化できます。面接やアルゴリズム学習において頻出のテーマなので、ぜひマスターしておきましょう。