AtCoder Beginner Contest 110 C – String Transformation をPython3で解く

Share

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典:
AtCoder Beginner Contest 110 C – String Transformation

最終的には、2つの文字列の構造が同じかどうかということが問われている。そこまで分かれば、素直に実装していけばいい。

# AtCoder Beginner Contest 110 C - String Transformation
# https://atcoder.jp/contests/abc110/tasks/abc110_c
# tag: 文字列 考察

# 文字列上の 2 つの文字が
# 1) 同じ文字の場合は、異なる文字に変えることが出来ず
# 2) 異なる文字の場合は、同じ文字に変えることが出来ない

# よって、各文字のある場所の対応が、S と T で
# 同一である必要がある。

# そこで、各文字列を頭から見ていき、
# その文字が初めて登場した場合は 0, 1, 2 と順に数字を当て、
# 既出の文字なら対応する数字を当てはめる数列を作成する。
# この数列が S と T で一致すれば、構造が一致している
# ことになる……という方針で。

def main():
S = input()
T = input()

# 文字列 → 数列の関数
def s_to_nlist(st):
tmp = 0
result = []

# 文字 → 数字の対応辞書
sn = dict()

for c in st:
# 初めての文字なら対応する数字を用意する
if c not in sn:
sn[c] = tmp
tmp += 1
# 対応する数字を数列に加える
result.append(sn[c])
return result

# 生成された数列が同じなら 'Yes'
if s_to_nlist(S) == s_to_nlist(T):
print('Yes')
else:
print('No')

main()
Share

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です