C - String Transformation

競プロ

はじめに

競技プログラミング、AtCoder Beginner Contest 110
C - String Transformation
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

英小文字のみからなる文字列S,Tが与えられます。
文字列Sに対して、次の操作を何度でも行うことができます。

操作: 2つの異なる英小文字c1,c2を選び、Sに含まれる全てのc1を c2に、c2を c1に置き換える

0回以上操作を行って、SをTに一致させられるか判定してください。

制約

・1≤|S|≤2×10^5
・|S|=|T|
・S,Tは英小文字のみからなる

入力

入力は以下の形式で標準入力から与えられる。

S
T

出力

SをTに一致させられる場合は Yes、そうでない場合は No を出力せよ。

解き方

こちらの解き方を参考にしています。
https://img.atcoder.jp/abc110/editorial.pdf
atcoder.jp

問題文に書かれている「操作」を行い、SをTに一致させられるかを考える。
まず例題を見ながら考え方を考えていく。

入力例１

azzel
apple

「azzel」を「apple」に書き換える。

①一番初めの「a」は両者共通の位置にあるので放置する

②二番目の文字は「azzel」は「z」だが、「apple」は「p」なので
「操作」を行い、
「azzel」の「z」を「p」に置き換え、「p」を「z」に置き換える。
「azzel」は「p」を含まないので「z」だけが「p」に置き換わり「appel」になる。

③三番目の文字は②の「操作」によって両者とも「p」になっているので放置する

④四番目の文字は「appel」は「e」だが、「apple」は「l」なので
「操作」を行い、「appel」の「e」を「l」に置き換え、「l」を「e」に置き換える。
「appel」は「e」「l」をどちらも含むので
それぞれが置き換わり「apple」になる。

⑤「azzle」は「apple」になるので答えは"Yes"

入力例2

chokudai
redcoder

①一文字目は「c」と「r」で異なっているので「操作」を行い、
「chokudai」の「c」を「r」に「r」を「c」に置き換える。
「chokudai」は「rhokudai」になる。

②二文字目は「h」と「e」で異なっているので「操作」を行い、
「rhokudai」の「h」を「e」に「e」を「h」に置き換える。
「rhokudai」は「reokudai」になる。

③三文字目は「o」と「d」で異なっているので「操作」を行い、
「reokudai」の「o」を「d」に「d」を「o」に置き換える。
「reokudai」は「redkuoai」になる。

④四文字目は「k」と「c」で異なっているので「操作」を行い、
「redkuoai」の「k」を「c」に「c」を「k」に置き換える。
「redkuoai」は「redcuoai」になる。

⑤五文字目は「u」と「o」で異なっているので「操作」を行い、
「redcuoai」の「u」を「o」に「o」を「u」に置き換える。
「redcuoai」は「redcouai」になる。

⑥六文字目は「u」と「d」で異なっているので「操作」を行い、
「redcouai」の「u」を「d」に「d」を「u」に置き換える。
「redcouai」は「reucodai」になる。

ここで③で置き換えた「d」が「u」に置き換わってしまうことに注目する。
「u」を「d」に置き換えたいが、
そうすると⑥の「d」が「u」に置き換わってしまうので
どちらも置き換えるということができない。

⑦「chokudai」は「redcoder」にできないので答えは"No"

ここで入力例1と2を見てみると以下のような違いがあることに気づく。

入力例1

a→a
z→p
z→p
e→l
l→e

つまり

a→a
z→p
e→l
l→e

が成り立ち、かつ

a→a
p→z
p→z
l→e
e→l

つまり

a→a
p→z
l→e
e→l

が成り立つ。

入力例2

c→r
h→e
o→d
k→c
u→o
d→d
a→e
i→r

は成り立つが

r→c（衝突A）
e→h
d→o（衝突B）
c→k
o→u
d→d（衝突B）
e→a
r→i（衝突A）

は成り立たない。

衝突Bは先ほどの⑥で起こった衝突である。
衝突Aが起こる前に成り立たないことが分かったので、
最後の「r」の置換までは進めていないが
そこまで進めれば
⑥の衝突Bと同じようにAも衝突することが分かる。

つまり、文字列SとTでそれぞれ文字列の置換表を作成し
置換表に合わないものがあれば
「操作」によってSをTにすることはできないということになる。

全体のコード

using System;
using System.Linq;
using System.Collections.Generic;

class Cmondai
{
    static void Main()
    {
        var S = Console.ReadLine();
        var T = Console.ReadLine();
        //対応表
        //S→T
        var dicST = new Dictionary<char, char>();
        //T→S
        var dicTS = new Dictionary<char, char>();
        //答え
        var ans = "Yes";
        //SとTの文字数ぶん、ループを回して
        //それぞれの文字の対応表への登録と照らし合わせを行う
        for (int i = 0; i < S.Length; ++i)
        {
            //S→T
            //登録されていない場合は登録する
            if (!dicST.ContainsKey(S[i])) dicST.Add(S[i], T[i]);
            //登録されている場合
            else
            {
                //対応表通りの文字になっているかを確認
                if (T[i] != dicST[S[i]])
                {
                    ans = "No";
                    break;
                }
            }

            //T→S
            //登録されていない場合は登録する
            if (!dicTS.ContainsKey(T[i])) dicTS.Add(T[i], S[i]);
            //登録されている場合
            else
            {
                //対応表通りの文字になっているかを確認
                if (S[i] != dicTS[T[i]])
                {
                    ans = "No";
                    break;
                }
            }
        }
        Console.WriteLine(ans);
    }
}