Вариация нахождения расстояния редактирования только с вставками и удалениями?

Question

Мне нужно найти расстояние редактирования между словом и его отсортированным словом (например, 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)

Какие изменения необходимо внести, чтобы найти только количество вставок и удалений?

Answer 1

Удалить 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.