LeetCode:72. Edit Distance

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:

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')

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')

可以通过插入、删除、替换三种操作将一个字符串变为另一个字符串，给定两个字符串，找出这两个字符串的最小编辑距离（操作次数）。

思路：动态规划

设i是字符串1中的某个位置，j是字符串2中得某个位置，在(i,j)处之前的两个字串的最小编辑距离为cost(i,j)。

首先，如果i位置的字符c1和j位置的字符c2相等，表明(i,j)处不需要操作，所以cost(i,j) = cost(i-1,j-1)。

其次，如果c1和c2不相等，则会有三种情况将word1变换到word2：

• cost(i,j) = cost(i-1,j)+1 对应了删除wrod1中i处这个字符的操作。
• cost(i,j) = cost(i,j-1)+1 对应了在wrod1中i处这插入个字符的操作。
• cost(i,j) = cost(i-1,j-1)+1 对应了在wrod1中i处替换一个字符的操作。

然后取三个操作对应的最小值即可也就是cost(i,j) = min(cost(i-1,j), cost(i,j-1), cost(i-1, j-1)) + 1。

用上面的 horse 和 ros 举例：

1. (i,j) = (0,0)，通过替换操作将h变为r，cost(0,0) = 1；
2. (i,j) = (0,1)，在(0,0)基础上通过插入o将h变为ro，cost(0,1) = 2；
3. (i,j) = (0,2)，在(0,1)基础上通过插入s将h变为ros，cost(0,2) = 3；
4. (i,j) = (1,0)，通过删除和替换操作将ho变为r，cost(1,0) = 2；
5. (i,j) = (1,1)，通过替换操作将ho变为ro，cost(1,1) = 1；
6. 依次类推。

最终得到如下表格：

#	0	1 , r	2 , o	3 , s
0	0	1	2	3
1 , h	1	1	2	3
2, o	2	2	1	2
3 , r	3	2	2	2
4 , s	4	3	3	2
5 , e	5	4	4	3

Python 代码实现

class Solution:
    # 参考 : https://leetcode.com/problems/edit-distance/discuss/25849/Java-DP-solution-O(nm)
    
    def minDistance(self, word1: str, word2: str) -> int:
        m = len(word1)
        n = len(word2)
        cost = [[0 for i in range(n+1)] for j in range(m+1)]

        for i in range(m+1):
            cost[i][0] = i
        for i in range(n+1):
            cost[0][i] = i
 
        for i in range(m):
            for j in range(n):
                if(word1[i] == word2[j]):
                    cost[i + 1][j + 1] = cost[i][j]
                else:
                    a = cost[i][j]
                    b = cost[i][j + 1]
                    c = cost[i + 1][j]
                    cost[i + 1][j + 1] = min(a,min(b,c))+1
        return cost[m][n];

参考：

Java-DP-solution-O(nm)

---

THE END.