C++で同型文字列（アイソモーフィック）を判定する方法

同型文字列とは？

2つの文字列 s と t が与えられたとき、両者が「同型（isomorphic）」であるかどうかを判定する問題を考えてみましょう。同型文字列とは、s の文字を適切に置き換えることで t が得られるような文字列のペアのことです。

ただし、置き換えには以下のルールがあります。

• ある文字が出現する箇所は、すべて同じ文字に置き換えなければなりません
• 文字の出現順序は保持される必要があります
• 2つの異なる文字が同じ文字へマップされることは許されません
• ただし、1つの文字が自分自身にマップされることは可能です

例えば、s = "egg"、t = "add" という入力の場合、e → a、g → d という一対一の対応関係が成り立つため、出力は true になります。

解法のアルゴリズム

この問題は、各文字の対応関係（マッピング）を記録しながら文字列を走査することで効率的に解けます。手順は以下の通りです。

1. サイズ256の配列 arr を定義し、すべて -1 で初期化します（文字間のマッピングを記録）
2. サイズ256の配列 visited を定義し、すべて 0 で初期化します（s 側の文字の使用状況を管理）
3. サイズ256の配列 visited1 を定義し、すべて 0 で初期化します（t 側の文字の使用状況を管理）
4. i := 0 から文字列 s の長さ未満の間、i を1ずつ増やしながら以下の処理を繰り返します。
   • visited[s[i]] が 1、または visited1[t[i]] が 1 の場合：
     • arr[s[i]] が t[i] - 'a'（ASCIIコードの差分）と等しくなければ false を返します
   • そうでない場合：
     • visited[s[i]] := 1 と設定します
     • visited1[t[i]] := 1 と設定します
     • arr[s[i]] := t[i] - 'a' としてマッピングを登録します
5. ループが最後まで完了したら true を返します

C++実装例

それでは、実際のC++コードを見ていきましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        vector<int> arr(256, -1);
        vector<bool> visited(256, 0);
        vector<bool> visited1(256, 0);
        for (int i = 0; i < s.length(); i++) {
            if (visited[s[i]] == 1 || visited1[t[i]] == 1) {
                if (arr[s[i]] != t[i] - 'a') {
                    return false;
                }
            }
            else {
                visited[s[i]] = 1;
                visited1[t[i]] = 1;
                arr[s[i]] = t[i] - 'a';
            }
        }
        return true;
    }
};
main(){
    Solution ob;
    cout << (ob.isIsomorphic("sky","fry"));
}

入力

"sky","fry"

出力

1

コードの解説

この例では、"sky" と "fry" を比較しています。s → f、k → r、y → y という一対一の対応が正しく成り立つため、結果として 1（true）が出力されます。

このアルゴリズムのポイントは、visited と visited1 という2つの使用済みフラグ配列を用意している点です。これにより、「s の異なる複数の文字が t の同じ1文字にマップされる」という不正なケースも確実に検出できます。例えば s = "ab"、t = "aa" の場合、最初の a → a というマッピングが登録された後、b → a を登録しようとした時点で visited1['a'] が既に 1 になっているため、正しく false と判定されます。

計算量は、文字列の長さを n とすると時間計算量 O(n)、固定サイズの配列のみを使用するため空間計算量 O(1) となり、非常に効率的な実装と言えます。