文字の置き換えで文字列を別の文字列に変換できるか判定するプログラム（C++実装）

問題の概要

2つの小文字のみで構成された文字列 s と t が与えられているとします。ここで、「s 内に現れる特定の文字をすべて別の文字へ置き換える」という操作を考えます。この操作は何度でも繰り返し実行できるものとし、s を t に変換できるかどうかを判定するのが目的です。

例えば、入力が s = "eye"、t = "pip" の場合、出力は True となります。「e」をすべて「p」に置き換え、その後「y」を「i」に置き換えることで変換できるからです。

解法のアプローチ

この問題は、文字ごとの対応関係（マッピング）をハッシュマップに記録しながら文字列を走査することで解決できます。s の各文字が t のどの文字に対応するかを管理し、矛盾が生じた時点で変換不可能と判断します。

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

• マップ m1 と m2 を定義する
• n を文字列 s の長さとする
• i を 0 で初期化し、i < n の間、i を 1 ずつ増やしながら以下を繰り返す
  • s[i] が m1 に存在する場合
    • m1[s[i]] が t[i] と一致していれば、次の反復へ進む
    • 一致していなければ、false を返す
  • 存在しない場合は、m1[s[i]] に t[i] を登録する
• ループが最後まで完了すれば true を返す

C++ による実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
bool solve(string s, string t) {
    map<char, char> m1, m2;
    int n = s.size();
    for(int i = 0; i < n; i++){
        if(m1.count(s[i])){
            if(m1[s[i]] == t[i]) continue;
            return false;
        }
        else{
            m1[s[i]] = t[i];
        }
    }
    return true;
}
int main(){
    string s = "eye", t = "pip";
    cout << solve(s, t);
}

入力

"eye","pip"

出力

1

計算量とまとめ

このアルゴリズムは文字列を一度だけ走査するため、文字列の長さを n とすると時間計算量は O(n) となります。また、マップが保持するキーはアルファベットの種類に限られるため、空間計算量は実質 O(1) と非常に効率的です。対応関係の矛盾を即座に検出できるこの手法は、文字列の同型性判定の基本的なアプローチとして広く知られています。