1

Given two lists of 1s and 0s called A and B of the same length, I want to determine if there is some way of inserting exactly n 1s or 0s into A and exactly n 1s or 0s into B to make them the same list. n will always be less than the lengths of the lists.

For example, set n = 2. Let A = [0,0,1,1,0,0] and B = [0,1,0,1,0,1]. We can transform A into [0,1,0,1,0,1,0,0] by inserting a 1 and a 0. B can be made into the same list by add two 0s at the right hand end.

Is there a known way to compute such a function

def match(A,B,n):
    return True if A and B are exactly insertion distance n from a common list

?

4

1 回答 1

2

算法

您可以通过修改标准编辑距离算法来找到最小插入次数 (x) 以使两个字符串相同来解决此问题。

当且仅当 x<=2*n 时，您的问题是可解决的。

Python代码：

A = [0,0,1,1,0,0]
B = [0,1,0,1,0,1]

def match(A,B,n):
    r = len(A)
    if r != len(B):
        return False
    DP = [ [0]*(r+1) for i in range(r+1) ]
    # DP[a][b] is min insertions to A to turn A[:a] and B[:b] into the same string
    for b in range(r+1):
        for a in range(r+1):
            if a>0 and b>0:
                best = DP[a-1][b-1]
                if A[a-1]!=B[b-1]:
                    best += 2 # inserting into both
            elif a==0 and b==0:
                best = 0
            else:
                best = 2*n+1

            if a>0:
                best = min(best,1+DP[a-1][b]) # inserting into A
            if b>0:
                best = min(best,1+DP[a][b-1]) # inserting into B
            DP[a][b] = best
    x = DP[r][r] # we have needed to make x insertions to get A and B to match
    # A and B are now the same length, so we must have made x/2 insertions to each
    return x<=2*n

print match(A,B,2)

解释

在您的情况下，您需要将 1 和 0 添加到 A，并将两个 0 添加到 B，因此 x（插入总数）将为 4。

请注意，您可能会担心该算法不会为两个字符串提供相等数量的插入。例如，它可能会找到一个解决方案，将 3 个字符添加到 A，将 1 个字符添加到 B。但是，这不可能是一个解决方案，因为这样字符串会变成不同的长度。

如果 x 小于 2*n，您可以简单地用相同的字符填充两个字符串，直到您设法将 n 个字符添加到每个字符串。

于 2013-09-23T19:54:50.660 回答