Determine if all elements in a list are present and in the same order in another list
list, python, sublist
Solution
Here's one way to do it in linear time (and constant space) with an iterator:
def sublist(a, b):
seq = iter(b)
try:
for x in a:
while next(seq) != x: pass
else:
return True
except StopIteration:
pass
return False
Basically it goes through each element of the sublist, and sees if it can find that same element in the part of the complete list it hasn't looked at yet. If it makes it through the entire sublist it means we have a match (hence the else statement on the for loop). If we run out of elements to look at in the complete list, it means we don't have a match.
Edit: I have updated my solution so it works with Python 3. For Python 2.5 and older, `next(seq)` needs to be replaced with `seq.next()`.
Problem
How do I create a function `sublist()` that takes two lists, `list1` and `list2`, and returns `True` if `list1` is a sublist of `list2`, and `False` otherwise. `list1` is a sublist of `list2` if the numbers in `list1` appear in `list2` in the same order as they appear in `list1`, but not necessarily consecutively. For example, ``` >>> sublist([1, 12, 3],[25, 1, 30, 12, 3, 40]) True >>> sublist([5, 90, 2],[90, 20, 5, 2, 17]) False ```