AtCoder Beginner Contest 110 - C

beta.atcoder.jp

直観とテストケースに頼って実装してしまった。学びにならないのでよくない。

def solve(S, T):
    sm = {}
    tm = {}
    for s, t in zip(S, T):
        if s in sm and sm[s] != t:
            return "No"
        sm[s] = t

        if t in tm and tm[t] != s:
            return "No"
        tm[t] = s

    return "Yes"


if __name__ == "__main__":
    S = input()
    T = input()
    print(solve(S, T))

改めて考えてみる。 Sの中に含まれるある文字で構成されるグループは、置き換えによって文字そのものは変わるものの、 そのグループの位置は変わらない。 そして、このグループは統合することも分割することもできない。

SからTに変換するための必要条件として、グループの構成が常に同じになる＝S中のある文字に対して、T側が常に同じ文字で対応する、というのがあげられる。 S->Tの対応だけを考えてしまうと以下のようなケースが通ってしまうため、T->S側の対応も確認し、常に同じグループであることを確認する。

S = bbbbcccc T = aaaaaaaa

って感じでよいのかな。