AOJ Course Edit Distance (Levenshtein Distance)

競技プログラミング

好きなアニメは、旦那が何を言っているかわからない件。えぬわいです。

qiita.com

続きです。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_E&lang=jp

レーベンシュタイン距離というのがあるらしい。

手のつけ方がわからなかったので、wikiと参考サイトを参照した。

mathwords.net

ここがわかりやすかった。それとwiki。

方針としては、2 つの文字列それぞれの連続する部分文字列を比較していくようだ。

文字数が違う場合は、前のものから +1 する必要がある。実際のDPでは、表がずれているので、注意が必要。

s1 = input()
s2 = input()

dp = [[0 for j in range(len(s2)+1)] for k in range(len(s1)+1)]

for i in range(len(s1)+1):
    dp[i][0] = i

for i in range(len(s2)+1):
    dp[0][i] = i

for i in range(0, len(s1)):
    for j in range(0, len(s2)):
        cost = 0 if s1[i] == s2[j] else 1
        dp[i+1][j+1] = min(dp[i][j+1]+1, dp[i+1][j]+1, dp[i][j]+cost)

print(dp[len(s1)][len(s2)])

DPテーブルは、

dp[i+1][j+1] := s1 の i 番目までと、s2 の j 番目までのレーベシュタイン距離

になっていると思われる。