Python describe LeetCode 72. Edit distance

Hello everyone , I'm Qi Guanjie （qí guān jié ）, stay 【 Qi Guanjie 】 official account 、CSDN、GitHub、B Share some technical blog posts on the website and other platforms , It mainly includes front-end development 、python The backend development 、 Applet development 、 Data structure and algorithm 、docker、Linux Common operation and maintenance 、NLP And other related technical blog , Time flies , Future period , come on. ~

If you love bloggers, you can focus on the bloggers' official account. 【 Qi Guanjie 】(qí guān jié), The articles inside are more complete and updated faster . If you need to find a blogger, you can leave a message at the official account. , I will reply to the message as soon as possible .

---

This article was originally written as 【 Qi Guanjie 】（qí guān jié ）, Please support the original , Some platforms have been stealing blog articles maliciously ！！！ All articles please pay attention to WeChat official account 【 Qi Guanjie 】.

subject

Here are two words for you word1 and word2, Please return to word1 convert to word2 The minimum number of operands used .

You can do the following three operations on a word ：

• Insert a character
• Delete a character
• Replace a character

Example 1：

 Input ：word1 = "horse", word2 = "ros"
Output ：3
explain ：
horse -> rorse ( take 'h' Replace with 'r')
rorse -> rose ( Delete 'r')
rose -> ros ( Delete 'e')

Example 2：

 Input ：word1 = "intention", word2 = "execution"
Output ：5
explain ：
intention -> inention ( Delete 't')
inention -> enention ( take 'i' Replace with 'e')
enention -> exention ( take 'n' Replace with 'x')
exention -> exection ( take 'n' Replace with 'c')
exection -> execution ( Insert 'u')

Tips ：

• 0 <= word1.length, word2.length <= 500
• word1 and word2 It's made up of lowercase letters

Their thinking

Dynamic programming .

dp[i][j] Express word1[:i] and word2[:j] The minimum editing distance of
about d[i][j] Come on
1. If word1[i-1] == word2[j-1], That is, the current letter is the same , No additional editing is required dp[i][j] = dp[i-1][j-1]
2. If word1[i-1] ！= word2[j-1], There are three ways to make them consistent
1. stay word1[i-1] Add characters after , here dp[i][j] = dp[i-1][j] + 1
2. stay word2[j-1] Add a character after , here dp[i][j] = dp[i][j-1] + 1
3. modify word1[i-1] by word2[j-1], here dp[i][j] = dp[i-1][j-1]+1
dp[i][j] = min(dp[i-1][j] + 1,dp[i][j-1] + 1,dp[i-1][j-1]+1)

Python describe

class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n,m = len(word1),len(word2)
dp = [[0 for _ in range(m+1)] for __ in range(n+1)]
for i in range(m+1):
dp[0][i] = i
for i in range(n+1):
dp[i][0] = i
for i in range(1,n+1):
for j in range(1,m+1):
if word1[i-1] != word2[j-1]:
dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
else:
dp[i][j] = dp[i-1][j-1]
return dp[n][m]