#72 Edit Distance——Top 100 Liked Questions

妖狐艹你老母 2022-01-29 03:09 229阅读 0赞

Given two words *word1* and *word2*, find the minimum number of operations required to convert *word1* to *word2*.

You have the following 3 operations permitted on a word:

1.  Insert a character
2.  Delete a character
3.  Replace a character

**Example 1:**

Input: word1 = "horse", word2 = "ros"
    Output: 3
    Explanation: 
    horse -> rorse (replace 'h' with 'r')
    rorse -> rose (remove 'r')
    rose -> ros (remove 'e')

**Example 2:**

Input: word1 = "intention", word2 = "execution"
    Output: 5
    Explanation: 
    intention -> inention (remove 't')
    inention -> enention (replace 'i' with 'e')
    enention -> exention (replace 'n' with 'x')
    exention -> exection (replace 'n' with 'c')
    exection -> execution (insert 'u')

> """
> 
> 第一次：动态规划，分插入：d\[i-1\]\[j\]+1，删除：d\[i\]\[j-1\]+1，替换：d\[i-1\]\[j-1\] + (word1\[i-1\] != word2\[i-1\])三种情况  
> """
> 
>     class Solution(object):
>         def minDistance(self, word1, word2):
>             """
>             :type word1: str
>             :type word2: str
>             :rtype: int
>             """
>             m = len(word1)
>             n = len(word2)
>             if m == 0:
>                 return n
>             if n == 0:
>                 return m
>             dp = [[0 for i in range(n + 1)] for j in range(m + 1)]
>             for i in range(m + 1):
>                 dp[i][0] = i
>             for j in range(n + 1):
>                 dp[0][j] = j
>             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] + (word1[i - 1] != word2[j - 1]))
>             return dp[m][n]
> 
>   
> """
> 
> Runtime: 164 ms, faster than 57.95% of Python online submissions for Edit Distance.
> 
> Memory Usage: 14.9 MB, less than 53.46% of Python online submissions for Edit Distance.
> 
> """