最长公共子序列测试用例失败

Question

我已经在最长的公共子序列中实现了这个算法，我对每个可能的测试用例都进行了测试，它是有效的，但是当我把它提交给在线评分员时，它说它在案例11中失败了，我想不出任何可能的测试用例会破坏它。你能帮忙吗？它返回idx longest子序列。在

def lcs2(a, b):
    idx = 0
    for i in a:
        if i not in b:
            a.remove(i)
    if len(a) <= len(b):
        for i in a:
           if i in b:
               idx += 1; b = b[b.index(i)+1:]

    else:
        for i in b:
           if i in a:
               idx += 1; a = a[a.index(i)+1:]
    return idx

Answer 1

您似乎要搜索的不是最长的公共子序列，而是这个最长公共子序列的长度。但是，错误的假设是，两个列表中的第一个列表包含该子序列的开头，其索引早于第二个列表。在

提供的答案已经给出了发生这种情况的示例：

a = [1,2,3,4,5]
b = [2,3,4,1,5]

我将扩展：

^{pr2}$

你会看到：

import itertools as it
rets = [lcs2(x,y) for x,y in it.permutations([a,b,c],2)]
combis = [(x,y) for x,y in it.permutations(['a','b','c'],2)]
print(*zip(rets, combis), sep='\n')
#(2, ('a', 'b'))
#(2, ('a', 'c'))
#(4, ('b', 'a'))
#(3, ('b', 'c'))
#(3, ('c', 'a'))
#(4, ('c', 'b'))

换句话说，您定义的lcs2函数是a对称的，因此不正确。在

Answer 2

我可以给你一个样本： a=[1,2,3,4,5] b=[2,3,4,1,5]

一个正确的解决方案是动态规划