Pythonで文字列同士を1対1にマッピングできるか判定するプログラムの書き方

問題の概要

2つの小文字からなる文字列 s と t が与えられたとします。このとき、s 内の各文字を別の文字(同じ文字でも可)へ1対1対応でマッピングすることで、s を t に変換できるかどうかを判定するのが本記事のテーマです。なお、文字の並び順は変更しないものとします。

例えば、入力が s = "papa"、t = "lili" の場合、出力は True になります。これは「p → l」「a → i」というマッピングを作成できるためです。

逆に、同じ文字が異なる文字にマッピングされようとした場合(例えば「p」が一度「l」に対応したのに、後で「m」に対応しようとする場合)や、異なる文字が同じ文字に重複してマッピングされる場合は False を返す必要があります。

解決のアプローチ

この問題は、双方向の辞書(マップ)を使うことで効率的に解けます。片方向だけのチェックでは、複数の文字が同じ文字にマッピングされるケースを見逃してしまうため、s → t と t → s の両方向を管理するのがポイントです。

具体的な手順は以下の通りです。

• s 用の辞書 s_dict と、t 用の辞書 t_dict をそれぞれ空の状態で用意する。
• i を 0 から s と t の長さのうち短い方までループさせる。
• s[i] がすでに s_dict に存在する場合:
  s_dict[s[i]] が t[i] と一致しなければ False を返す。
• t[i] がすでに t_dict に存在する場合:
  t_dict[t[i]] が s[i] と一致しなければ False を返す。
• どちらにも存在しない場合は、新しい対応関係として両方の辞書に登録する。
• ループが最後まで完了したら True を返す。

実装例(Python)

以下が実際のコード実装です。

class Solution:
    def solve(self, s, t):
        s_dict = {}
        t_dict = {}
        for i in range(min(len(s), len(t))):
            if s[i] in s_dict:
                if s_dict[s[i]] != t[i]:
                    return False
            elif t[i] in t_dict:
                if t_dict[t[i]] != s[i]:
                    return False
            else:
                s_dict[s[i]] = t[i]
                t_dict[t[i]] = s[i]
        return True

ob = Solution()
print(ob.solve("papa", "lili"))

入力

"papa", "lili"

出力

True

コードの解説

このアルゴリズムでは、文字列を先頭から順に走査しながら、以下の2種類の矛盾を検出します。

• 一貫性の欠如: 同じ文字が異なる文字へマッピングされようとした場合(s_dict でチェック)。
• 衝突: 異なる文字が同じ文字へマッピングされようとした場合(t_dict でチェック)。

どちらのチェックも通過できれば、その時点でのマッピングは有効であり、最終的に True が返されます。

計算量について

時間計算量は O(n)(n は文字列の長さ)、空間計算量も O(n) となります。各文字の照会・登録は辞書によって平均 O(1) で行えるため、非常に効率的です。

まとめ

2つの辞書を用いて双方向のマッピングを管理することで、文字列同士が1対1で対応付け可能かどうかを線形時間で判定できます。同様の考え方は、同型(isomorphic)文字列の判定など、他の文字列マッピング系の問題にも応用できます。