检查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 sublistExists(list, sublist):
    for i in range(len(list)-len(sublist)+1):
        if sublist == list[i:i+len(sublist)]:
            return True #return position (i) if you wish
    return False #or -1

正如马克提到的，这种搜索方法并不是最有效的（它的复杂度是O(n*m)）。这个问题可以用类似于字符串搜索的方法来解决。

Answer 2

让我们来点儿函数式编程的内容，好吗？ :)

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

请注意，any() 这个函数会在找到第一个匹配的子列表时就停止搜索。如果没有找到匹配的，它会在进行 O(m*n) 次操作后失败。

Answer 3

如果你确定输入的数据只会是单个数字0和1，那么你可以把它们转换成字符串：

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

这样做会创建两个字符串，所以效率不是最高的解决方案。不过，由于Python有优化过的字符串搜索算法，这种方法对于大多数情况来说应该是足够好的。

如果效率非常重要，你可以看看Boyer-Moore字符串搜索算法，它可以调整用来处理列表。

简单的搜索方法在最坏情况下的时间复杂度是O(n*m)，但如果你不能使用字符串转换的方法，并且不太关心性能，这种方法也是可以的。