时间戳

首页 > 解决方案 > 以递归方式编辑距离相似算法

algorithm - 以递归方式编辑距离相似算法

问题描述

我的任务是找到二进制整数数组之间的“编辑距离”，例如：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
}

如何从这里开始？

标签： algorithmrecursion

解决方案

您总共有四个选项删除最左边的位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)。我认为你不能只是从任何你想要的地方插入或删除字符这一事实实际上使它的复杂性更高。不过我觉得可以减少。

推荐阅读