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

最小编辑距离定义
【第十三天（《LeetCode一天一例》-----两个字符串之间的最小编辑距离（python实现））】将一个字符串变成另外一个字符串所用的最少操作数，每次只能增加、删除或者替换一个字符。
例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 dpif __name__ == '__main__': word1 = 'daaqerdwq' word2 = 'aswdreqew' dp = minDist(word1, word2) for i in dp: print(i)

输出结果：