计算两个字符串之间的差异（Levenshtein距离）

Question

我正在尝试计算两个字符串之间的距离。两个字符串之间的距离/差异指的是将一个字符串改变为另一个字符串所需的最小字符插入、删除和替换次数。

我尝试的方法是：将两个字符串转换为列表，进行比较，检查区别，然后添加区别。

first_string = "kitten"
second_string = "sitting"

list_1 = list(first_string)
list_2 = list(second_string)

print("list_1 = ", list_1)
print("list_2 = ", list_2)
print("   ")


lengths =  len(list_2) - len(list_1)
new_list = set(list_1) - set(list_2)
print(lengths)
print(new_list)

difference = lengths + int(new_list)
print(difference)

我得到的输出是：

list_1 =  ['k', 'i', 't', 't', 'e', 'n']
list_2 =  ['s', 'i', 't', 't', 'i', 'n', 'g']

1
{'e', 'k'}

我正在尝试找出如何添加这些差异以使其等于3。我不知道如何使输出类似，从而将它们加在一起（将1与{'e'，'k'}相加，使距离为3）。

- The Wonderer

Answer 1

你已经接近成功了。使用len()函数计算new_list的长度，就像你在lengths中所做的一样：

difference = lengths + len(new_list)

- drumstick2121

Answer 2

看起来你只需要更改这行代码：

difference = lengths + int(len(new_list))

那应该可以给你想要的3个 :)，最初的回答。

- Giannis Katsini

Answer 3

这被称为Levenshtein距离。可以查看这个实现来进一步了解。最初的回答。

- Ekkaia153