C#で2つの文字列が同型（Isomorphic）かどうかを判定する方法

同型文字列とは？

2つの文字列XとYにおいて、X内の各文字の出現箇所をすべて別の文字に置き換えることでYが得られ、その逆も成り立つ場合、XとYは「同型（isomorphic）」であるといいます。

例として、文字列「ACAB」と「XCXY」を考えてみましょう。すべての文字の出現箇所は、文字の並び順を保ったまま別の文字へ置き換える必要があります。ここで重要なルールは次のとおりです。

• 各文字は常に同じ文字にのみ対応づけられる
• 異なる2つの文字が同じ文字に対応することはできない
• ただし、ある文字が自分自身に対応することは許される

実行例

例1：同型の場合

入力：s = "egg"、t = "add"

出力：true

e→a、g→dという対応関係が一貫して成立するため、これらの文字列は同型です。

例2：同型でない場合

入力：s = "foo"、t = "bar"

出力：false

2つ目の文字oに対してaへの対応が必要ですが、3つ目の文字oにはrへの対応が必要になります。同じ文字が異なる文字に対応することは許されないため、falseとなります。

時間計算量：O(N)
空間計算量：O(N)

C#での実装コード

public class Arrays{
    public bool IsStringIsomorphic(string s, string t){
        if (s == null || t == null){
            return false;
        }
        int[] chars1 = new int[128];
        int[] chars2 = new int[128];
        for (int i = 0; i < s.Length; i++){
            if (chars1[s[i]] != chars2[t[i]]){
                return false;
            }
            else{
                chars1[s[i]] = i + 1;
                chars2[t[i]] = i + 1;
            }
        }
        return true;
    }
}

static void Main(string[] args){
    Console.WriteLine(s.IsStringIsomorphic("add", "egg"));
}

コードの解説

このアルゴリズムでは、長さ128のint型配列を2つ用意し、各文字が最後に出現した位置（インデックス+1）を記録します。ループ処理の中で、s[i]とt[i]に対応する記録値が一致しない場合は即座にfalseを返し、一致する場合は両方の配列に現在の位置を登録していきます。

2つの配列を使うことで、s→t方向とt→s方向の双方のマッピングの一貫性を同時に検証できるのがポイントです。これにより、「egg」と「add」のような正しい対応はtrueと判定され、「foo」と「bar」のように対応が矛盾するケースはfalseと判定されます。

実行結果

True