用python代码,计算两个单词之间的编辑距离
时间: 2023-12-03 22:41:56 浏览: 36
编辑距离(英语:Edit distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。
以下是Python代码实现:
```python
def edit_distance(str1, str2):
len1, len2 = len(str1), 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] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
return dp[len1][len2]
```
其中,`str1`和`str2`是要比较的两个单词。函数返回它们之间的编辑距离。例如,对于单词"python"和"pycharm",它们之间的编辑距离为2。