第十三天：《LeetCode一天一例》-----两个字符串之间的最小编辑距离（python实现）

我会带着你远行 2022-01-30 03:29 167阅读 0赞

### 最小编辑距离定义 ###

将一个字符串变成另外一个字符串所用的最少操作数，每次只能增加、删除或者替换一个字符。

**例1： **                                                                                                                                                                                                 输入: word1 = "horse", word2 = "ros"  
     输出: 3  
     解释:  
        horse -> rorse (replace 'h' with 'r')  
        rorse -> rose (remove 'r')  
        rose -> ros (remove 'e')

**例2:**  
     输入: word1 = "intention", word2 = "execution"  
     输出: 5  
     解释:  
        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')

### 例子引出算法 ###

我们有两个词汇，word1为michaelab ， word2 为 michaelxy。 （这里我们为了比较容易理解，使用word1和word2的长度假定相等。） dp \[i\] \[j\] 作为word1转换为word2的最小编辑距离，  我们就是要计算这个矩阵。

显然如果b==y, 那么dis\[i\]\[j\] = dis\[i-1\]\[j-1\]  也就是从后面看起，如果两个字符串的最后一个字符相同，那我们就看dis\[i-1\]\[j-1\]。  
     假设word1\[i\]和word2\[j\](此处i = j)分别为：michaelab和michaelxy     我们规定三种操作：添加，删除，替换

如果b!=y，那么：

**    添加：**也就是在michaelab后面添加一个y，那么word1就变成了michaelaby，此时

dis\[i\]\[j\] = 1 + dis\[i\]\[j-1\]；

上式中，1代表刚刚的添加操作，添加操作后，word1变成michaelaby，word2为michaelxy。dis\[i\]\[j-1\]代表从word\[i\]转换成word\[j-1\]的最小Edit Distance，也就是michaelab转换成michaelx的最小Edit Distance，由于两个字符串尾部的y==y，所以只需要将michaelab变成michaelx就可以了，而他们之间的最小Edit Distance就是dis\[i\]\[j-1\]。

**    删除：**也就是将michaelab后面的b删除，那么word1就变成了michaela，此时

dis\[i\]\[j\] = 1 + dis\[i-1\]\[j\]；

上式中，1代表刚刚的删除操作，删除操作后，word1变成michaela，word2为michaelxy。dis\[i-1\]\[j\]代表从word\[i-1\]转换成word\[j\]的最小Edit Distance，也就是michaela转换成michaelxy的最小Edit Distance，所以只需要将michaela变成michaelxy就可以了，而他们之间的最小Edit Distance就是dis\[i-1\]\[j\]。

**    替换：**也就是将michaelab后面的b替换成y，那么word1就变成了michaelay，此时

dis\[i\]\[j\] = 1 + dis\[i-1\]\[j-1\]；

上式中，1代表刚刚的替换操作，替换操作后，word1变成michaelay，word2为michaelxy。dis\[i-1\]\[j-1\]代表从word\[i-1\]转换成word\[j-1\]的最小Edit Distance，也即是michaelay转换成michaelxy的最小Edit Distance，由于两个字符串尾部的y==y，所以只需要将michaela变成michaelx就可以了，而他们之间的最小Edit Distance就是dis\[i-1\]\[j-1\]。

### python代码实现 ###

def minDist(word1, word2):
    	len1 = len(word1)
    	len2 = len(word2)
    	dp = [[0 for i in range(len1+1)] for j in range(len2+1)]
    	print(dp)    # 构造dp矩阵 
    	i = 0 
    	for item in dp:
    		item[0] = i
    		i += 1
    	i = 0
    	for i in range(len1+1):
    		dp[0][i] = i
    		i += 1
    
    	for i in range(1, len1+1):
    		for j in range(1, len2+1):
    			if word1[i-1] == word2[j-1]:
    				dp[i][j] = dp[i-1][j-1]
    			else:
    				insert = 1 + dp[i][j-1]
    				delete = 1 + dp[i-1][j]
    				replace = dp[i-1][j-1] + 1
    				dp[i][j] = min(insert, delete, replace)
    	return dp
    
    
    if __name__ == '__main__':
    	word1 = 'daaqerdwq'
    	word2 = 'aswdreqew'
    	dp = minDist(word1, word2)
    	for i in dp:
    		print(i)

输出结果：

![20190517214445165.png][]

可以看出 最右下角元素为2  所以最小编辑距离为2

图太难画了，，我真的不想画

[20190517214445165.png]: /images/20220130/f5c89a47a0244b1daafb6bae54d81134.png