Python 中是否有一个内置函数可以返回两个列表的最长公共子序列的长度?
我试图找到最长公共子序列,然后获取其长度,但我认为必须有更好的解决方案。
a=[1,2,6,5,4,8]
b=[2,1,6,5,4,4]
print a.llcs(b)
>>> 3
我试图找到最长公共子序列,然后获取其长度,但我认为必须有更好的解决方案。
a=[1,2,6,5,4,8]
b=[2,1,6,5,4,4]
print a.llcs(b)
>>> 3
def lcs_length(a, b):
table = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i, ca in enumerate(a, 1):
for j, cb in enumerate(b, 1):
table[i][j] = (
table[i - 1][j - 1] + 1 if ca == cb else
max(table[i][j - 1], table[i - 1][j]))
return table[-1][-1]
演示:
>>> a=[1,2,6,5,4,8]
>>> b=[2,1,6,5,4,4]
>>> lcs_length(a, b)
4
def lcsubstring_length(a, b):
table = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
longest = 0
for i, ca in enumerate(a, 1):
for j, cb in enumerate(b, 1):
if ca == cb:
length = table[i][j] = table[i - 1][j - 1] + 1
longest = max(longest, length)
return longest
lcs_length
方法非常相似,但我们跟踪目前为止找到的最大长度(因为不再保证表中的最后一个元素是最大值)。3
:>>> lcsubstring_length(a, b)
3
一种稀疏表的变体,不需要跟踪所有的 0
(如果 a
和 b
可能非常大,则使用此选项):
def lcsubstring_length(a, b):
table = {}
longest = 0
for i, ca in enumerate(a, 1):
for j, cb in enumerate(b, 1):
if ca == cb:
length = table[i, j] = table.get((i - 1, j - 1), 0) + 1
longest = max(longest, length)
return longest
xrange()
,只需使用 range()
。 - juanbretti
[2, 6, 5, 4]
,因此 长度 是 4。 - Martijn Pieters[2, 6, 5, 4]
,并且顺序相同。在a
中,这些元素是连续的,但在b
中有一个值在它们之间(1
),但它是a
和b
的子序列。 - Martijn Pieters