[leetcode] 72. Edit Distance
問題の説明
リンク
文字列1を文字列2に変更する最も簡単な方法のステップ数をinsert/delete/replaceで求める
1-DP 2 Dに近い
dp[i][j] =word 1[:i+1]およびword[:j+1]dp[0][j] = j 空文字列をj=j回追加dp[i][0] = iiを空の文字列にする方法=i回削除word1[i] == word2[j] => dp[i+1][j+1] = dp[i][j] word1[i] != word2[j] => dp[i+1][j+1] =(端数ベース)dp[i][j]horsとro比較dp[i][j+1]horsとros比較dp[i + 1][j]horsesとro比較# dp[i+1][j+1]
dp[i+1][j+1] = dp[i][j] if word1[i]==word2[j]
else min(dp[i][j], dp[i+1][j], dp[i][j+1]) + 1
# 1은 costコード1
def minDistance(word1, word2):
m, n = len(word1), len(word2)
dp = [list(range(n+1))]+[[r+1]+[0]*n for r in range(m)]
for i in range(m):
for j in range(n):
dp[i+1][j+1] = dp[i][j] if word1[i]==word2[j] else min(dp[i][j], dp[i+1][j], dp[i][j+1]) + 1
return dp[m][n]2 D DPに近い1 D DP
コード2
def minDistance(word1, word2):
m, n = len(word1), len(word2) # switch word1 and word2 if m < n to ensure n ≤ m
curr = list(range(n+1))
for i in range(m):
prev, curr = curr, [i+1] + [0] * n
for j in range(n):
curr[j+1] = prev[j] if word1[i] == word2[j] else min(curr[j], prev[j], prev[j+1]) + 1
return curr[n]
Reference
この問題について([leetcode] 72. Edit Distance), 我々は、より多くの情報をここで見つけました https://velog.io/@youn_22/leetcode-72.-Edit-Distanceテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol