检查Python中是否存在切片列表

Question

我想编写一个函数来确定子列表是否存在于更大的列表中.

list1 = [1,0,1,1,1,0,0]
list2 = [1,0,1,0,1,0,1]

#Should return true
sublistExists(list1, [1,1,1])

#Should return false
sublistExists(list2, [1,1,1])

有没有Python功能可以做到这一点？

Answer 1

让我们有点功能,好吗？:)

def contains_sublist(lst, sublst):
    n = len(sublst)
    return any((sublst == lst[i:i+n]) for i in xrange(len(lst)-n+1))

注意 any()将在lst内的第一个匹配停止 - 如果没有匹配则失败,在O(m*n)操作之后停止

Answer 2

如果您确定输入只包含单个数字0和1,那么您可以转换为字符串:

def sublistExists(list1, list2):
    return ''.join(map(str, list2)) in ''.join(map(str, list1))

这创建了两个字符串,因此它不是最有效的解决方案,但由于它利用了Python中优化的字符串搜索算法,它可能足以满足大多数目的.

如果效率非常重要,您可以查看Boyer-Moore字符串搜索算法,该算法适用于列表.

一个天真的搜索有O(n*m)最坏的情况,但如果你不能使用转换为字符串技巧并且你不需要担心性能,那么它可能是合适的.