ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC110 C - String Transformation

問題
提出コード
この問題、個人的にはD問題より難しかったです…

解法

Sの中から1つ文字を選択したとき、Sの中の同じ文字はすべて、置換後も同じ文字になってしまいます。そのため、S="aa"、T="bc"のようなものは答えがNoになります。
なので、Sの中である文字の種類を1つ選択したとき、Tの部分もすべて同じ種類の文字になっていないといけません。

また、Tの中から1つ文字を選択したとき、Tの中の同じ文字はすべて、置換前も同じ文字でないといけません。そのため、S="ab"、T="cc"のようなものは答えがNoになります。
なので、1つめの条件と同様に、Tの中である文字の種類を1つ選択したとき、Sの部分もすべて同じ種類の文字になっていないといけません。

ということで、26×26マスのテーブルをつくり、片方が置換前の文字、もう片方が置換後の文字とします。
S、Tについて全探索をし、SとTの文字について、テーブル上の対応する場所にビットをたてます。
そして、最後にすべての行、および列についてチェックし、その行(列)上でビットがたっている数が0、もしくは1になっていればSからTに置換することができます。
2個以上ビットが立っている行(列)が1つでも存在したら、答えはNoになります。