检查Python中是否存在切片列表 [英] Check for presence of a sliced list in Python

问题描述

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

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函数?

解决方案

如果您确定输入内容仅包含数字0和1，则可以转换为字符串:

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

这会创建两个字符串，因此它不是最有效的解决方案，但是由于它利用了Python中优化的字符串搜索算法，因此对于大多数目的来说可能已经足够好了.

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

天真搜索的最坏情况为O(n * m)，但如果您不能使用转换为字符串技巧并且您不必担心性能，则可能会很合适.

I want to write a function that determines if a sublist exists in a larger list.

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])

Is there a Python function that can do this?

解决方案

If you are sure that your inputs will only contain the single digits 0 and 1 then you can convert to strings:

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

This creates two strings so it is not the most efficient solution but since it takes advantage of the optimized string searching algorithm in Python it's probably good enough for most purposes.

If efficiency is very important you can look at the Boyer-Moore string searching algorithm, adapted to work on lists.

A naive search has O(n*m) worst case but can be suitable if you cannot use the converting to string trick and you don't need to worry about performance.

这篇关于检查Python中是否存在切片列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！