Pythonで解く「バディ文字列」問題：1回のスワップで2つの文字列を一致させられるか判定する

問題の概要

小文字だけで構成された2つの文字列 A と B が与えられたとします。このとき、A の中から2文字を選んで入れ替える（スワップする）操作をちょうど1回行うことで、A を B と一致させることができるかどうかを判定するのが「バディ文字列（Buddy Strings）」問題です。

例えば、入力が A = "ba"、B = "ab" の場合、先頭の2文字を入れ替えるだけで両者は一致するため、出力は True になります。

解法のアプローチ

この問題は、以下の手順に沿って判定することで効率的に解けます。

• A と B の長さが異なる場合は False を返します。そもそも文字数が違えば、どんなスワップを行っても一致させることはできません。
• A と B をそれぞれソートした結果が異なる場合（＝使われている文字の種類や個数が一致しない場合）は False を返します。文字の構成が同じでなければ、順序の入れ替えだけでは一致しません。
• A と B が完全に同一で、かつ A に含まれる文字がすべてユニーク（重複なし）である場合は False を返します。同一の文字列でも重複した文字が存在すれば、その2つを入れ替えても見た目は変わらないため True になり得ますが、すべてユニークな場合は必ずどこかが不一致になってしまいます。
• 上記以外の場合は、各位置の文字を順番に比較して不一致の箇所をカウントします。カウントが3になった時点で False を返します（不一致箇所が2か所以内でなければ、1回のスワップでは一致させられないため）。ループが完了すれば True を返します。

なお、ソート済みの文字構成が一致しているという前提があるため、不一致箇所の数は必然的に偶数（0または2）になります。したがって「count == 3」のチェックで、3か所以上の不一致を確実に検出できます。

実装例

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

class Solution:
    def buddyStrings(self, A, B):
        if len(A) != len(B):
            return False
        elif sorted(A) != sorted(B):
            return False
        elif A == B and len(set(A)) == len(A):
            return False
        else:
            count = 0
            for i in range(len(A)):
                if A[i] != B[i]:
                    count += 1
                    if count == 3:
                        return False
        return True

ob = Solution()
print(ob.buddyStrings("ba", "ab"))

入力

"ba", "ab"

出力

True

計算量について

この解法の時間計算量は O(n log n)（ソート処理がボトルネック）、空間計算量は O(n) となります。n は文字列の長さです。ソートを使わずに文字の出現数をカウントする方式（Counterなど）を採用すれば、時間計算量を O(n) まで改善することも可能です。