编辑距离相似算法递归

Question

我得到了一个任务来找到二进制INT e.g的阵列之间的“编辑距离”：011011和这样的

有3个选项：1。从左边右边2.拆下位删除位，3无能为力

现在，如果我们移除位的距离被减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删除最右边的位。尝试所有四个oprions和取最小值。下面是使用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)。你不能只是插入或从你真正想要的任何地方删除字符的事实使得复杂性更高，我认为。我认为这虽然可以降低。