72. Edit Distance

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• 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')
1
2
3
4
5
6

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')
1
2
3
4
5
6
7
8

Constraints:

• 0 <= word1.length, word2.length <= 500
• word1 and word2 consist of lowercase English letters.

动态规划解法

在 3 个算子中选择最小的成本

• 删除：dp(i-1, j) + 1
• 插入：dp(i, j-1) + 1
• 代替：dp(i-1, j-1) + 1

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        len1 = len(word1)
        len2 = len(word2)
        if len1 == 0: return len2
        if len2 == 0: return len1
        
        table = [[0] * (len2 + 1) for _ in range(len1 + 1)]
        
        for r in range(len1 + 1):
            table[r][0] = r
        for c in range(len2 + 1):
            table[0][c] = c
        
        for r in range(1, len1 + 1):
            for c in range(1, len2 + 1):
                if word1[r - 1] == word2[c - 1]:
                    table[r][c] = table[r - 1][c - 1]
                else:
                    table[r][c] = 1 + min(table[r - 1][c], table[r][c - 1], table[r - 1][c - 1])
        
        return table[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

参考

https://leetcode.com/problems/edit-distance/discuss/159295/Python-solutions-and-intuition

https://leetcode.com/problems/edit-distance/discuss/1475220/Python-3-solutions-Top-down-DP-Bottom-up-DP-O(N)-in-Space-Clean-and-Concise