ABC110 C - String Transformation

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import string

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = list(iss())
    T = list(iss())
    StoT = {}
    TtoS = {}
    for n in range(ord('a'), ord('z') + 1):
        StoT[chr(n)] = 0
        TtoS[chr(n)] = 0

    for st in zip(S, T):
        s, t = st
        if StoT[s] == 0 and TtoS[t] == 0:
            StoT[s] = t
            TtoS[t] = s
        elif StoT[s] != t or TtoS[t] != s:
            print('No')
            exit()
    else:
        print('Yes')


if __name__ == '__main__':
    main()

考え方

文字列Sの英小文字が文字列Tの英小文字に対応しているか、
文字列Tの英小文字が文字列Sの英小文字に対応しているかを全て確認する。
つまり、文字列Sのある英小文字が文字列Tのある英小文字と対応しているとき、
別の箇所に存在する英小文字も同じ英小文字と1対1で対応しているか否かを確認する。

例えば、文字列S = 'azzel'、文字列T = 'apple'のとき、
先頭から順にみていくと、

1. 文字列Sにおけるaは文字列Tにおけるaに対応している
2. 文字列Sにおけるzは文字列Tにおけるzに対応している
3. 文字列Sにおけるzは文字列Tにおけるzに対応している（2. に矛盾していない）
4. 文字列Sにおけるeは文字列Tにおけるlに対応している
5. 文字列Sにおけるlは文字列Tにおけるeに対応している (4. に矛盾していない）

と、各英小文字が1対1で対応しているため、変換することは可能である。

文字列S = 'chokudai'、文字列T = 'redcoder'のとき、
先頭から順にみていくと、

1. 文字列Sにおけるcは文字列Tにおけるrに対応している
2. 文字列Sにおけるhは文字列Tにおけるeに対応している
3. 文字列Sにおけるoは文字列Tにおけるdに対応している
4. 文字列Sにおけるkは文字列Tにおけるcとなっているが、
   英小文字cは1.でrと対応しているため、1対1の条件に当てはまらない。
   そのため、変換は不可能であるとわかる。