[AtCoder]ABC110 C-String Transformation

AtCoder

Photo by Magda Ehlers on Pexels.com

2022.04.27

Table of Contents

問題

C - String Transformation

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

方針

はじめは

from collections import Counter

でCounterを出して、Counterの構造に着目して\(\cdots\)なんてやっていたが、駄目だった。

s = translate(str.maketrans(s[i), t[i], s)

で実際にsの文字をtに置き換えて行く作戦も、\(0(N^2)\)かかるのでTLEに。

ここで方針を転換して、要するにsの文字とtの文字が単射になっていればswapでsからtを構成できるので、単射を実装してみる。

解答

#input
s = list(input())
t = list(input())

#output
from collections import defaultdict
d1 = defaultdict(set)
d2 = defaultdict(set)
n = len(s)

for i in range(n):
    d1[ord(t[i])].add(ord(s[i]))
    d2[ord(s[i])].add(ord(t[i]))

answer = "Yes"
for i in d1.values():
    if len(i) > 1:
        answer = "No"
for i in d2.values():
    if len(i) > 1:
        answer = "No"
print(answer)

提出結果

Submission #31307995 - AtCoder Beginner Contest 110

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

補足

defaultdictは便利。呼び出すとき

d_set = defaultdict(set)
d_list = defaultdict(list)

としておくと、

d_set[some_key].add(some_value)
d_list[some_key].append(some_value)

で一つのkeyに対して重複してvalueをもたせる事ができる。

defaultdict(set,
            {114: {99, 105},
             101: {97, 104},
             100: {100, 111},
             99: {107},
             111: {117}})

解答ではこれを利用して、\(s\rightarrow t\)と\(t \rightarrow s\)のそれぞれに対して辞書を作成し、valueが二つ以上になったら駄目という判定にしている。