Pythonでアナグラムかどうかを判定する方法

2つの文字列 s0 と s1 が与えられたとき、それらが互いにアナグラムであるかどうかを判定する問題について解説します。アナグラムとは、一方の文字列に含まれる文字を並べ替えることで、もう一方の文字列と完全に一致させることができる関係のことです。

例えば、入力が s0 = "listen"、s1 = "silent" の場合、「listen」の文字を並べ替えると「silent」となるため、出力は True になります。

解決のアプローチ

この問題は、以下の手順でシンプルに解くことができます。

• s0 と s1 のそれぞれの文字をソートする
• ソート後の文字列同士を比較する
• 両者が一致すれば True を返し、一致しなければ False を返す

アナグラムであれば、使用されている文字とその個数が必ず同じになるため、ソート後の結果も同一になると考えられます。

実装例

以下のコードでは、Pythonの組み込み関数 sorted() を活用しています。文字列を sorted() に渡すと、文字ごとにソートされたリストが返されるため、それらを直接比較するだけで判定が完了します。

class Solution:
    def solve(self, s0, s1):
        return sorted(s0) == sorted(s1)

ob = Solution()
print(ob.solve("listen", "silent"))

入力

"listen", "silent"

出力

True

計算量とより効率的な方法

上記の方法の時間計算量は、文字列の長さを n とすると O(n log n) です。さらに効率を求める場合は、collections.Counter を使って各文字の出現回数を比較する方法が有効です。この場合、計算量は O(n) に改善できます。

from collections import Counter

class Solution:
    def solve(self, s0, s1):
        return Counter(s0) == Counter(s1)

どちらの方法でも簡潔にアナグラム判定を実装できますが、文字列が非常に長いケースでは Counter を使う方法がパフォーマンス面で有利です。