Pythonで1回の文字スワップにより2つの文字列を等しくできるか判定するプログラム

同じ長さの2つの文字列 s と t があるとします。ここで考える操作とは、ある文字列の中から2つのインデックス(必ずしも異なる必要はありません)を選び、その位置の文字同士を入れ替えることです。本記事では、どちらか一方の文字列に対して最大1回のスワップを実行することで、2つの文字列を同じにできるかどうかを判定する方法を解説します。

たとえば、入力が s = "hello"、t = "hlelo" の場合、どちらか一方の文字列で e と l を入れ替えるだけで2つの文字列が一致するため、出力は True になります。

アルゴリズムの流れ

この問題は、以下の手順で解決できます。

• 許容される差の上限 max_diffs を 2 に設定します。
• 実際の差の個数 diffs を 0 で初期化します。
• s の文字を格納する集合 st と、t の文字を格納する集合 st2 を新しく作成します。
• i を 0 から s の長さまで順番に処理します。
  • s[i] と t[i] が異なる場合は、diffs を 1 増やします。
  • s[i] が st に存在しなければ、st に追加します。
  • t[i] が st2 に存在しなければ、st2 に追加します。
  • diffs が max_diffs を超えた場合は、即座に False を返します。
• 最終的に、「diffs が 0 または 2」かつ「st と st2 のサイズが等しい」かつ「st と st2 の内容が一致する」場合に True を返し、それ以外は False を返します。

判定条件のポイント

最後の条件式が成り立つ理由は以下の通りです。

• diffs == 0 の場合: 2つの文字列は最初から一致しているため、スワップは一切不要です。
• diffs == 2 の場合: 異なる位置がちょうど2箇所あり、さらに両方の文字列に含まれる文字の種類が完全に一致していれば、1回のスワップで一致させることができます。
• その他の場合: 差が3箇所以上あると1回のスワップでは修正できません。また、差の位置があっても文字の構成(集合)が異なる場合、スワップによって一致させることは不可能です。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def solve(s, t):
    max_diffs = 2
    diffs = 0
    st = set()
    st2 = set()
    for i in range(len(s)):
        if s[i] != t[i]:
            diffs += 1
        if s[i] not in st:
            st.add(s[i])
        if t[i] not in st2:
            st2.add(t[i])
        if diffs > max_diffs:
            return False
    return (diffs == 0 or diffs == 2) and len(st) == len(st2) and st == st2

s = "hello"
t = "hlelo"
print(solve(s, t))

入力

"hello", "hlelo"

出力

True