Levenshtein算法python实现
时间: 2023-09-30 09:05:03 浏览: 63
Levenshtein算法是计算字符串之间的编辑距离的一种算法。以下是一个Python实现代码示例:
```python
def levenshtein_distance(str1, str2):
len1 = len(str1)
len2 = len(str2)
dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]
for i in range(len1 + 1):
dp[i][0] = i
for j in range(len2 + 1):
dp[0][j] = j
for i in range(1, len1 + 1):
for j in range(1, len2 + 1):
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
return dp[len1][len2]
```
使用方法:
```python
str1 = "kitten"
str2 = "sitting"
distance = levenshtein_distance(str1, str2)
print(distance)
```
输出结果为 3,表示将 "kitten" 转换为 "sitting" 的编辑距离为 3。