admin 管理员组

文章数量: 1086019


2024年4月14日发(作者：个人博客的图片大全)

两个字符串编辑距离计算python3实现

在Python3中，可以使用动态规划算法来计算两个字符串的编辑距

离。编辑距离（Edit Distance）是指将一个字符串转换成另一个字符

串所需的最小操作次数，操作包括插入、删除和替换字符。以下是一

个Python3实现的示例：

```python

def edit_distance(str1, str2):

m, n = len(str1), len(str2)

dp = [[0] * (n + 1) for _ in range(m + 1)]

for i in range(m + 1):

dp[i][0] = i

for j in range(n + 1):

dp[0][j] = j

for i in range(1, m + 1):

for j in range(1, n + 1):

if str1[i - 1] == str2[j - 1]:

dp[i][j] = dp[i - 1][j - 1]

else:

dp[i][j] = min(

dp[i - 1][j], # 删除

dp[i][j - 1], # 插入

dp[i - 1][j - 1] # 替换

) + 1

return dp[m][n]

if __name__ == "__main__":

str1 = "kitten"

str2 = "sitting"

print("编辑距离：", edit_distance(str1, str2))

```

在这个示例中，我们计算了字符串 "kitten" 和 "sitting" 的编辑距离。

输出结果为：

```

编辑距离： 3

```

这表示将 "kitten" 转换为 "sitting" 需要进行3次操作，例如：将 "k"

替换为 "s"，将 "i" 插入 "gg"，将 "t" 替换为 "t"。


本文标签： 操作 计算 编辑

版权声明：本文标题：两个字符串编辑距离计算python3实现 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1713102098a619956.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。