ABC110 C問題

問題概要

英小文字のみからなる文字列 \(S, T\) が与えられる。

文字列 \(S\) に対して、次の操作を何度でも行うことができる。

• 2つの異なる英小文字 \(c_1, c_2\) を選び、\(S\) に含まれる全ての\(c_1\) を\(c_2\)に、\(c_2\) を\(c_1\)に置き換える

0回以上この操作を行って、\(S\)を\(T\)と一致させられるかを判定せよ。

制約

• 1 ≤ \(|S|\) ≤ 2 \(\times\) 10⁵
• \(|S| = |T|\)
• S, Tは英小文字のみからなる。

問題へのリンクはこちら

考えたこと

• alphabet のどの文字がどの文字に変換されるかという変換表を用意する
• 変換表が埋まっていない時には、変換表を埋める
• 変換表が埋まっていて、行き先が前の場合と今回の場合で異なっている時には失敗

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
  string S, T; cin >> S >> T;
  vector<int> start(26, -1); // -1 で埋めるように初期化
  vector<int> goal(26, -1);
  for(int i = 0; i < S.size(); i++) {
    int a = S[i] - 'a'; // char から int に変換
    int b = T[i] - 'a';

    if(start[a] != -1 || goal[b] != -1) {
      if(start[a] != b || goal[b] != a) {
        cout << "No" << endl;
        return 0;
      }
    } else {
      start[a] = b;
      goal[b] = a;
    }
  }
  cout << "Yes" << endl;
  return 0;
}