AtCoder Beginner Contest 110 - C - String Transformation
逆方向の変換も考えないといけないの思いつかなかった。
https://gyazo.com/3aa28edd9eff97b84ba487aba263e80c
解説を見て
S = aab, T = bczを考えてみる
1つ目のaはa -> b, 2つ目はa -> cにしないといけない、けれども操作は指定した文字全てをスワップ操作なので,
aが2つ以上に対応する場合は絶対に作れない
最初にa->bとしたらS = bbbとなる、a->cとすると,S = ccbとなる,どうやっても1文字目をbへ、2文字目をcにできない
S = bcz, T = aazも考える
b -> a, c -> aにしないといけない、一見できそうだけどこれもできない
b -> aをやると S = aczになる, 次にc -> aにしようとすると、スワップなのでS = cazになる(先にc -> aからやっても同じ)
成り立たない条件は
Sの中で同じもじが出た時、そこと対応するTの文字も毎回同じ
Tの中で同じもじが出た時、そこと対応するSの文字も毎回同じ
と言える、あとはsとtを先頭から順に見ていって、英小文字辞書みたいなの用意して同じ文字に対して複数対応するのがないか調べればいい
vector<set<char>> tmp(26)みたいなのを用意すれば楽
英小文字は26文字なので、26サイズのset<char> vectorを用意する
setは重複データを許容しないデータ構造なので、同じ文字だったらサイズ数が増えない
最後に全ての英小文字と対応する英小文字が全て1以下かを調べればいい
提出したコード
code: C.cpp
int main() {
string s,t; cin >> s >> t;
vector<set<char>> tmp1(26);
vector<set<char>> tmp2(26);
rep(i, s.size()) {
}
rep(i, 26) {
if(tmp1i.size() > 1 || tmp2i.size() > 1) { cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
return 0;
}