【Python】2つの文字列が同型（アイソモーフィック）かどうかを判定する方法

プログラミングにおける「同型」とは、一方の文字列に出現する各文字を、一対一の対応関係に基づいて別の文字へ置き換えることで、もう一方の文字列と完全に一致させられる関係を指します。たとえば「egg」と「add」は e→a、g→d という対応で一致するため同型ですが、「foo」と「bar」は o が2回登場する一方で r が1回しか登場しないため、対応が成立せず同型ではありません。

2つの文字列が同型であるかを確認するには、2つの文字列を引数として受け取る関数を定義します。この関数は文字列の長さ分だけループ処理を行い、組み込み関数 ord() を使って文字を整数（Unicodeコードポイント）に変換しながら、文字同士のマッピングが矛盾なく成立しているかを検証していきます。

サンプルコード

以下に実装例を示します。

MAX_CHARS = 256

def check_isomorphic(str_1, str_2):
    len_1 = len(str_1)
    len_2 = len(str_2)

    # 長さが異なる場合は同型になり得ない
    if len_1 != len_2:
        return False

    marked = [False] * MAX_CHARS  # 対応先として既に使われた文字を記録
    mapping = [-1] * MAX_CHARS    # 文字同士の対応関係を保持

    for i in range(len_2):
        if mapping[ord(str_1[i])] == -1:
            # 対応先の文字が既に別の文字に使われていれば同型ではない
            if marked[ord(str_2[i])] == True:
                return False
            marked[ord(str_2[i])] = True
            mapping[ord(str_1[i])] = str_2[i]
        elif mapping[ord(str_1[i])] != str_2[i]:
            # 登録済みの対応関係と矛盾する場合は同型ではない
            return False
    return True

str_1 = 'aab'
str_2 = 'xxy'
str_3 = 'xyz'

print("1つ目の文字列 :", str_1)
print("2つ目の文字列 :", str_2)
print("3つ目の文字列 :", str_3)
print(f"{str_1} と {str_2} は同型か？ →", check_isomorphic(str_1, str_2))
print(f"{str_1} と {str_3} は同型か？ →", check_isomorphic(str_1, str_3))

実行結果

1つ目の文字列 : aab
2つ目の文字列 : xxy
3つ目の文字列 : xyz
aab と xxy は同型か？ → True
aab と xyz は同型か？ → False

コードの解説

• check_isomorphic という名前の関数を定義します。
• この関数は2つの文字列を引数として受け取ります。
• まずそれぞれの文字列の長さを取得し、長さが異なる場合はその時点で False を返します。文字数が違えば一対一の対応は成立しないためです。
• 256個の要素を持つ2つのリストを用意します。1つは対応先として既に使用された文字を記録するため False で初期化されたリスト、もう1つは文字の対応関係を保存するため -1 で初期化されたリストです。
• 2番目の文字列の長さ分だけループし、1番目の文字列の各文字を ord() で整数に変換してインデックスとして扱います。
• まだマッピングが未登録の文字の場合、対応先の文字がすでに別の文字に使われていないかを確認し、問題なければ新しい対応関係を登録します。
• すでにマッピングが存在する場合は、現在の対応関係と一致しているかを検証し、矛盾があれば False を返します。
• すべての文字の検証を通過できれば、2つの文字列は同型であると判断され True を返します。
• 関数の外側で複数のテスト用文字列を用意し、それぞれの判定結果をコンソールに出力します。

計算量について

文字列の長さを n とすると、このアルゴリズムの時間計算量は O(n) です。補助配列のサイズは文字種の最大数（ここでは256）で固定されているため、空間計算量は O(1) とみなせます。ASCII文字のみを扱うケースでは、この固定サイズの配列方式がシンプルかつ高速に動作します。