72. edit distance

72. Edit distance

Original title link ：https://leetcode.cn/problems/edit-distance/

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 ：

Definition dp[i][j] Means ：word1 Before i Characters and word2 Before j Edit distance of characters . Namely word1 Before i Characters , become word2 Before j Characters , It takes at least so many steps . If one of the strings is empty , Then the edit distance is the length of another string ; When both strings are not empty ,dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+int(word1[i]!=word2[j]))：
for example ,word1 = “abcde”, word2 =“fgh”, Now let's calculate the editing distance between these two strings , Is to find from word1, At least how many steps , Can become word2？ There are three ways ：

know "abcd" become "fgh" How many steps （ hypothesis X Step ）, So from "abcde" To "fgh" Namely "abcde"->“abcd”->“fgh”.（ Delete... At a time , Add X Step , in total X+1 Step ）
know "abcde" become “fg” How many steps （ hypothesis Y Step ）, So from "abcde" To "fgh" Namely "abcde"->“fg”->“fgh”.（ First Y Step , Add again , Add X Step , in total Y+1 Step ）
know "abcd" become “fg” How many steps （ hypothesis Z Step ）, So from "abcde" To "fgh" Namely "abcde"->“fge”->“fgh”（ Replace ）.

Code implementation ：

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)

        if m * n == 0:
            return m + n

        #  Definition dp[i][j]:word1 To i The characters of   Transform into  word2[j]  Editor's distance 
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        #  initialization dp：word1 Empty or word2 It's empty , Then the minimum number of steps of conversion 
        #  Namely word1 or word2 The length of 
        for i in range(m + 1):
            dp[i][0] = i

        for j in range(n + 1):
            dp[0][j] = j
        
        #  according to dp[i - 1][j] dp[i][j - 1] dp[i - 1][j - 1]
        #  Calculation dp[i][j] Value 
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + int(word1[i - 1] != word2[j - 1]))

        return dp[m][n]

reference ：
https://leetcode.cn/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/