递归中的相似距离编辑算法

Question

我的任务是找出二进制整数数组之间的“编辑距离”，例如: 011011等等

有3个选项: 1.从右侧删除位2.从左侧删除位，3.不执行任何操作

现在，如果我们移除一个比特，距离就减少1，如果比特匹配，距离就增加1。

例如: s1=01010101 s2=10101010我们可以去掉s1 (-1)中最左边的位和s2 (-1)中最右边的位，得到s1=1010101和s_2=1010101，它是7-2=5

我正在尝试编写一个算法，并考虑到以下几点：

fun(s1,s2){
    if s1[i] == s2[i]
        score++
    else
        return min(fun(s1[n-1],s2),fun(s1,s2[n-1]),fun(s1+1,s2),fun(s1,s2+1))-1
}

如何从这里开始呢？

Answer 1

总共有四个选项从s1中删除最左边的位，从s1中删除最右边的位，从s2中删除最左边的位，从s2中删除最右边的位。尝试所有四种操作，并采取最低限度。这是一个在python中使用memoization的python解决方案。

memo = {}
def fun(s1, s2):
    if s1 == s2:
        return 0
    if (s1, s2) in memo:
        return memo[s1, s2]
    r = 1e10 # infinity
    if len(s1) > 0:
        # remove left bit from s1
        r = min(r, 1 + fun(s1[1:], s2))
        # remove right bit from s1
        r = min(r, 1 + fun(s1[:-1], s2))
    if len(s2) > 0:
        # remove left bit from s2
        r = min(r, 1 + fun(s1, s2[1:]))
        # remove right bit from s2
        r = min(r, 1 + fun(s1, s2[:-1]))
    memo[s1, s2] = r
    return r
fun('01010101', '10101010') # 2    

这可以通过使用子字符串的索引来进一步优化，而不是将字符串作为参数传递。时间复杂度为O(n^4)。事实上，你不能从你想要的任何地方插入或删除字符，这实际上使它变得更加复杂，我认为。但我认为它可以减少。