How to Efficiently Determine if a Sublist Exists in Python?

Detecting Sublist Presence in Python

The task at hand is to devise a function that verifies the existence of a sublist within a larger list. Given two lists, one as the larger list (list1) and the other as the potential sublist (list2), the function should determine whether list2 is indeed a sublist of list1.

Implementing the Function

Python provides a versatile function named any() that can be leveraged for this purpose. The following code snippet demonstrates how to construct a function that employs any():

<code class="python">def sublist_exists(lst, sublst):
    n = len(sublst)
    return any((sublst == lst[i:i+n]) for i in range(len(lst)-n+1))</code>

This function meticulously scans the larger list (lst) by iterating over its elements one by one. For each element at index i, it extracts a contiguous sublist of length n and compares it to the potential sublist (sublst). If a match is detected, the function immediately returns True, indicating the presence of the sublist. This process continues until either a match is found or the entire larger list has been exhausted, in which case the function returns False.

Performance Considerations

It's important to note that the time complexity of this function is O(m*n), where m is the length of the larger list and n is the length of the potential sublist. For each iteration, the function performs a sublist comparison operation, and the number of iterations is constrained by the difference between m and n plus one.

Example Usage

Let's illustrate the usage of the sublist_exists function with the provided examples:

<code class="python">>>> sublist_exists([1,0,1,1,1,0,0], [1,1,1])
True

>>> sublist_exists([1,0,1,0,1,0,1], [1,1,1])
False</code>

In the first example, [1,1,1] is indeed a sublist of the larger list, so the function returns True. In the second example, [1,1,1] does not appear in the larger list, so the function returns False.

The above is the detailed content of How to Efficiently Determine if a Sublist Exists in Python?. For more information, please follow other related articles on the PHP Chinese website!