【ABC177 B】「Substring」を解く【Python3】

コンテスト一覧へ

 

文字列S,Tがあり、TがSの部分文字列となるようにしたい場合、最低限、何文字置き換える必要があるのか答える問題です。

提出
s = input()
t = input()
ls = len(s)
lt = len(t)
ans = lt

for i in range(ls-lt+1):
    num = 0
    for j in range(lt):
        if s[i+j] != t[j]:
            num += 1
    ans = min(ans, num)

print(ans)

入力した文字列をs,tに代入し、長さも取得しておきます。

len()関数

len()関数は、引数で指定したオブジェクトの長さを返します。

文字列の場合は文字数、リストの場合は要素数を取得できます。

len(オブジェクト)

置き換える文字数は、最大、tの長さ分なので、「ans = lt」としておきます。

(ltが5の場合は、sの1〜5文字目、2〜6文字目、……、というように)sのすべての文字列の一部がtと何文字異なるかを調べていきます。

for i in range(ls-lt+1):

の「range(ls-lt+1)」という部分で、最後に調べる文字列を調節しています。

例えば、lsが9、ltが3の場合は、最後に調べる文字列は「7〜9文字目(0始まりだと6文字目から)」となるため、「range(ls)」では上手くいきません。

異なる文字数(=num)とansを比較して、小さい方をansに代入します。

最後にansに入っている値が答えとなります。

【ABC177】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。