Beginner Exercism • python

Sublist

Challenge Overview

Write a function to determine if a list is a sublist of another list.

Dig Deeper

List manipulation

The direct approach would be to manipulate and check the given lists to solve this. This solution uses a helper function, which simplifies things, but the approach can be implemented without it.

SUBLIST = 1
SUPERLIST = 2
EQUAL = 3
UNEQUAL = 4

def check_sub_sequences(list_one, list_two):
    n1 = len(list_one)
    n2 = len(list_two)
    return any(list_two[i:i+n1] == list_one for i in range(n2 - n1 + 1))
    
def sublist(list_one, list_two):
    if list_one == list_two:
        return EQUAL
    if check_sub_sequences(list_one, list_two):
        return SUBLIST
    if check_sub_sequences(list_two, list_one):
        return SUPERLIST
    return UNEQUAL

We first check for equality using the == operator, if so, then we return EQUAL. A common way to do this differently would be to return 1 directly, but this is better practice as we remove magic values.

After that we call check_sub_sequences passing in list_one and list_two. In the helper function, we check if any of the possible sub-sequences in list_two of length n1 (the length of the first list) are equal to the first list. If so, then we conclude that list_one is a SUBLIST of list_two.

To find whether list_one is a SUPERLIST of list_two, we just reverse this process - pass in the lists in the opposite order. Thus, we check if any of the possible sub-sequences in list_one of length n2 (the length of the second list) are equal to the second list.

If none of the above conditions are true, we conclude that the two lists are unequal.

Using strings

**This approach does not work, and this document exists to explain that.** 
Please do not use it in your code.

Another seemingly clever solution is to convert the lists to strings and then use the in operator to check for sub-sequences. Note that this approach, even if it worked, is not as performant as the previous one.

SUBLIST = 1
SUPERLIST = 2
EQUAL = 3
UNEQUAL = 4

def sublist(list_one, list_two):
    list_one_check = str(list_one).strip("[]")
    list_two_check = str(list_two).strip("[]")

    if list_one_check == list_two_check:
        return EQUAL
    elif list_one_check in list_two_check:
        return SUBLIST
    elif list_two_check in list_one_check:
        return SUPERLIST
    return UNEQUAL

Let’s parse the code to see what it does. In this approach, we convert the lists to strings, so [1, 2, 3] becomes "[1, 2, 3]", remove the brackets "1, 2, 3", and add a comma "1, 2, 3,". We check equality and then use the in operator to check for SUBLIST or SUPERLIST, and finally return UNEQUAL.

We add a comma because, say, we call sublist with [1, 2] and [1, 22]. "1, 2" in "1, 22" evaluates to True, so the function would wrongly mark it as SUBLIST.

This test can be overridden by changing the code like this:

list_one_check = str(list_one).strip("[]") + ','
list_two_check = str(list_two).strip("[]") + ','

Yet, the test case (which doesn’t exist in the Exercism test suite) ["1", "2"] and ["5", "'1', '2',", "7"] would fail.

Students can add any arbitrary string into the representation to try to “defeat” this test - list_one_check = str (list_one) + TOKEN. The test suite currently test TOKEN = '', but not others.

Source: Exercism python/sublist