莱文斯坦距离/最小编辑距离(python)

阅读: 评论:0

莱文斯坦距离/最小编辑距离(python)

莱文斯坦距离/最小编辑距离(python)

LeetCode题目链接:

/

本题的解题思路,和经典的动态规划问题:最长公共子序列是相似的,只不过一个求最大,一个求最小。

简单来说:如果我们要比较字符串‘abc’和字符串‘def’,而且已知:

  1. s1=‘ab’和s2=‘de’的最小编辑距离为k1,
  2. s1=‘abc’和s2=‘de’的最小编辑距离为k2,
  3. 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] = ifor 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已经有了相关的库去实现。见链接:

但是关于加权的最小编辑距离,我没有找到现成的方法,因此后续会讲解关于加权最小编辑距离的文章。见链接:

本文发布于:2024-02-01 20:44:52,感谢您对本站的认可!

本文链接:https://www.4u4v.net/it/170679148939315.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

标签:距离   最小   文斯   编辑   python
留言与评论(共有 0 条评论)
   
验证码:

Copyright ©2019-2022 Comsenz Inc.Powered by ©

网站地图1 网站地图2 网站地图3 网站地图4 网站地图5 网站地图6 网站地图7 网站地图8 网站地图9 网站地图10 网站地图11 网站地图12 网站地图13 网站地图14 网站地图15 网站地图16 网站地图17 网站地图18 网站地图19 网站地图20 网站地图21 网站地图22/a> 网站地图23