Levenshtein Distance算法python
时间: 2023-07-10 08:13:57 浏览: 53
以下是Levenshtein Distance算法的Python实现代码:
```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]
```
其中,str1和str2分别是两个字符串,m和n分别是它们的长度。首先,我们初始化编辑距离矩阵dp,并把第一行和第一列分别初始化为0到n和0到m。然后,我们依次计算dp矩阵中的每一个元素,如果str1的第i个字符等于str2的第j个字符,则dp[i][j]等于dp[i-1][j-1],否则,dp[i][j]等于dp[i-1][j]、dp[i][j-1]和dp[i-1][j-1]中的最小值加1。最后,dp[m][n]就是str1和str2之间的编辑距离。