Блог

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