仅通过插入和删除查找编辑距离的变化?

Variation of finding edit distance with only insertions and deletions?

我需要找到一个词与其排序词之间的编辑距离(例如:apple 和 aelpp),仅递归地使用插入和删除。

我找到了一些使用插入、删除和替换的资源,但我不确定如何只使用插入和删除。

这是我找到的代码:

def ld(s, t):
    if not s: return len(t)
    if not t: return len(s)
    if s[0] == t[0]: return ld(s[1:], t[1:])
    l1 = ld(s, t[1:])
    l2 = ld(s[1:], t)
    l3 = ld(s[1:], t[1:])
    return 1 + min(l1, l2, l3)

需要做哪些编辑才能只找到插入和删除的数量?

删除 l3,它会像这样计算替换

def ld2(s, t):
    if not s: return len(t)
    if not t: return len(s)
    if s[0] == t[0]: return ld2(s[1:], t[1:])
    l1 = ld2(s, t[1:])
    l2 = ld2(s[1:], t)
    return 1 + min(l1, l2)

您可以看到 ld('apple', 'applx') 等于 1,而具有相同参数的 ld2 的计算结果为 2。