ABC076 C – Dubious Document 2

はじめに

競プロの精進のために学びがあった問題についてまとめています。 目標は AtCoder 水色！

今のレートは茶色です。

問題

ABC076 C - Dubious Document 2を解きました。

難易度は緑色。

考察

後方から貪欲的に一致する文字列を探していって、最初に見つかったもの以外の？はすべて”a”で埋めると辞書順最小になる。

サンプルは通ったが、「len(Sd) と len(T)」の長さが一致した場合の考慮漏れで1ペナしてしまったので大いに反省。

コード

Sd = input()[::-1]
T = input()[::-1]

for i in range(len(Sd) + 1 - len(T)):
    f = True
    for j, t in enumerate(T):
        if t != Sd[i+j] and Sd[i+j] != '?':
            f = False
            break
            
    if f:
        ans = []
        for k in range(len(Sd)):
            if Sd[k] == '?':
                ans.append("a")
            else:
                ans.append(Sd[k])

        for j, t in enumerate(T):
            ans[i+j] = t

        print("".join(ans[::-1]))
        exit()

print("UNRESTORABLE")

まとめ

ペナ予防のために、範囲の端と端を含むかちゃんと確認する。