编辑距离计算python
时间: 2023-07-04 11:24:35 浏览: 66
编辑距离(Edit Distance),又称Levenshtein距离,是指两个字符串之间,由一个转成另一个所需的最少编辑操作次数。
常见的编辑操作有:
1. 插入一个字符
2. 删除一个字符
3. 替换一个字符
下面是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]
```
其中,dp[i][j]表示str1的前i个字符转换成str2的前j个字符所需的最少编辑操作次数。
例如,对于字符串"horse"和"ros",可以通过以下编辑操作将"horse"转换为"ros":
1. 把"h"替换成"r"
2. 删除"o"
3. 删除"r"
4. 把"e"替换成"s"
因此,编辑距离为4。