概述
LeetCode题目链接:
https://leetcode-cn.com/problems/edit-distance/
本题的解题思路,和经典的动态规划问题:最长公共子序列是相似的,只不过一个求最大,一个求最小。
简单来说:如果我们要比较字符串‘abc’和字符串‘def’,而且已知:
- s1=‘ab’和s2=‘de’的最小编辑距离为k1,
- s1=‘abc’和s2=‘de’的最小编辑距离为k2,
- s1=‘ab’和s2=‘def’的最小编辑距离为k3,
那我们知道我们有三种可能得到原问题的解:
情况一:s1=‘ab’和s2=‘de’,先将‘abc’中的‘ab’变为‘de’,再将最后的c变为f,也就是编辑距离为k1+1.如果凑巧s1最后的字母和s2最后的字母相同,如‘abc’和‘dec’,那么最小编辑距离就是k1
情况二:s1=‘abc’和s2=‘de’,先将‘abc’变为‘de’,再在最后添加f,也就是编辑距离为k2+1.
情况三:s1=‘ab’和s2=‘def’,先将‘ab’变为‘def’,再把最后的c删除掉,也就是编辑距离为k3+1.
python代码如下:
def minDistance( word1: str, word2: str) -> int:
'''
动态规划求解
'''
m = len(word1)
n = len(word2)
print(m)
print(n)
dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
#注意初始化0串和别的串之间的编辑距离
for i in range(n+1):
dp[0][i] = i
for j in range(m+1):
dp[j][0] = j
# for i in range(m+1):
#
for j in range(n+1):
#
print(dp[i][j],end=' ')
#
print()
for i in range(1,1+m):
for j in range(1,1+n):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])
for i in range(m+1):
for j in range(n+1):
print(dp[i][j],end=' ')
print()
return dp[m][n]
# a = 'horse'
# b = 'ros'
# print(minDistance(a,b))
本文讲解的最小编辑距离,是不加权的。也就是说,增加、删除、修改操作所占的比重相同。关于不加权的莱文斯坦距离,python已经有了相关的库去实现。见链接:
https://blog.csdn.net/u014657795/article/details/90476489
但是关于加权的最小编辑距离,我没有找到现成的方法,因此后续会讲解关于加权最小编辑距离的文章。见链接:
https://blog.csdn.net/qq_36282995/article/details/116421271
最后
以上就是过时中心为你收集整理的莱文斯坦距离/最小编辑距离(python)的全部内容,希望文章能够帮你解决莱文斯坦距离/最小编辑距离(python)所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复