给定两个长度相同的 1 和 0 列表 A 和 B,我想确定是否有某种方法可以将 n 个 1 或 0 恰好插入 A 并恰好将 n 个 1 或 0 插入 B 以使它们相同列表。 n 将始终小于列表的长度。
例如,设置 n = 2。让 A = [0,0,1,1,0,0]
和 B = [0,1,0,1,0 ,1]
。我们可以通过插入一个 1 和一个 0 将 A 转换为 [0,1,0,1,0,1,0,0]
。通过在右手端。
有没有已知的方法来计算这样的函数
def match(A,B,n):
return True if A and B are exactly insertion distance n from a common list
?
最佳答案
算法
您可以通过修改 standard edit distance algorithm 来解决这个问题找到使两个字符串相同的最小插入次数 (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)
解释
在您的例子中,您需要向 A 添加一个 1 和一个 0,向 B 添加两个 0,因此 x(插入的总数)将为 4。
请注意,您可能担心该算法不会为两个字符串提供相同数量的插入。例如,它可能会找到一个解决方案,将 3 个字符添加到 A,将 1 个字符添加到 B。但是,这不是解决方案,因为这样字符串将变得不同长度。
如果事实证明 x 小于 2*n,您可以简单地用相同的字符填充两个字符串,直到您设法向每个字符串添加恰好 n 个字符。
关于python - 插入/删除列表之间的距离,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18967316/