Pythonで文字を入れ替えて、同じ長さの2つの文字列を等しくできるか判定する方法

問題の概要

長さnの2つの文字列 s と t があるとします。s から1文字、t から1文字を選んで入れ替える(スワップする)操作は何度でも行えます。このとき、2つの文字列を完全に等しくすることが可能かどうかを判定するのが課題です。

例えば、入力が s = "xy"、t = "yx" の場合、出力は True になります。

解法のアプローチ

この問題は、次の手順で解くことができます。

• s と t を連結した文字列 st を作成し、ソートします。
• st の先頭から2文字ずつペアとして確認します(インデックス0から開始し、2ずつ増やしながらループ)。
• st[i] と st[i+1] が異なる場合は、False を返します。
• すべてのペアが一致していれば、True を返します。

この方法が正しい理由は、スワップ操作によって任意の文字を片方の文字列からもう片方へ自由に移動できるためです。したがって、連結後の各文字の出現回数がすべて偶数であれば、その文字を s 側と t 側に同数ずつ振り分けることができ、必ず2つの文字列を一致させられます。逆に1つでも奇数回出現する文字があれば、等しくすることは不可能です。計算量はソートが支配的となり、O(n log n) となります。

実装例

以下のコードで、より具体的なイメージをつかみましょう。

サンプルコード

class Solution:
    def solve(self, s, t):
        st = sorted(s + t)
        for i in range(0, len(st), 2):
            if st[i] != st[i+1]:
                return False
        return True

ob = Solution()
print(ob.solve("xy", "yx"))

入力

"xy", "yx"

出力

True

まとめ

この問題のポイントは、「2つの文字列を連結してソートすれば、等しくできる条件は全文字種が偶数回出現すること」という性質に気づくことです。シンプルなソートとペア比較だけで O(n log n) で効率的に判定でき、実装も非常にわかりやすくなっています。