Pythonで2つの文字列が「近い」かどうかを判定するアルゴリズムと実装方法

問題の概要

2つの文字列 s と t が与えられたとき、この2つが「近い(close)」関係にあるかどうかを判定するプログラムを考えます。

次の2種類の操作を何度でも繰り返し適用することで、一方の文字列からもう一方の文字列を作り出せる場合、その2つの文字列は「近い」とみなされます。

• 既存の2文字を入れ替える:文字列内の任意の2文字の位置を交換できます。例:abcde → aecdb
• ある文字の出現箇所をすべて別の文字に変換する(同時に逆変換も行う):すべての 'a' を 'b' に、すべての 'b' を 'a' に変換するといった操作が可能です。例:aacabb → bbcbaa(ここではすべての a が b に、b が a に変換されています)

これらの操作は、どちらの文字列に対しても好きな回数だけ使用できます。

具体例

入力が s = "zxyyyx"、t = "xyyzzz" の場合、出力は True になります。3回の操作で s から t を作り出せるためです。

• "zxyyyx" → "zxxyyy"(文字の入れ替え)
• "zxxyyy" → "yxxzzz"(文字の一括変換)
• "yxxzzz" → "xyyzzz"(文字の入れ替え)

解き方のアプローチ

この問題を効率的に解くには、「近い」文字列が満たすべき条件に着目します。ポイントは次の2つです。

• 使用されている文字の種類が完全に一致していること:片方にしか存在しない文字がある場合、どのような操作を行っても一致させられません。
• 各文字の出現回数のリスト(頻度分布)が一致していること:文字の入れ替えは頻度を変えず、一括変換は頻度の対応関係を入れ替えるだけなので、ソート後の頻度リストが同一である必要があります。

以上を踏まえると、解法の手順は以下のようになります。

• s と t の間に共通しない文字が1つでも存在する場合は False を返す
• s に含まれる各文字の出現回数のリストを a とする
• t に含まれる各文字の出現回数のリストを b とする
• リスト a をソートする
• リスト b をソートする
• a と b が一致しない場合は False を返す
• それ以外は True を返す

Pythonでの実装例

以下のコードでは、collections.Counter を使って文字の出現頻度を簡単に集計しています。

from collections import Counter

def solve(s, t):
    if set(s) != set(t):
        return False
    a = list(Counter(s).values())
    b = list(Counter(t).values())
    a.sort()
    b.sort()
    if a != b:
        return False
    return True

s = "zxyyyx"
t = "xyyzzz"
print(solve(s, t))

入力

"zxyyyx", "xyyzzz"

出力

True

計算量について

文字種の集合比較は O(n)、頻度の集計も O(n)、ソートは最大でも文字種の数(英小文字なら高々26個)に対して行われるため、全体の時間計算量は O(n + k log k)(k は文字種の数)となり、非常に効率的です。