Python: Using list comprehensions to filter a list by a list of substrings

Question

I think this is a simple question, so I'll just go straight to an example.

Given these two lists:

x = ['a', 'ab', 'abc', 'bc', 'c', 'ac']
y = ['a', 'b']

How do I write a list comprehension to filter list x in such a way that the result would be:

result = ['c']

I want a list comprehension that excludes any partial matches of the strings in y to the strings in x. For example, 'a' in y would match 'a', 'ab', 'abc', and 'ac' in x.

This comprehension only matches entire strings: result = [r for r in x if r not in y]

If this has already been asked I'll gladly accept a link to a previous answer. That said, I haven't found one on SO yet.

Answer 1

Use all:

result = [r for r in x if all(z not in r for z in y)]

Or any:

result = [r for r in x if not any(z in r for z in y)]

Answer 2

This is a job for the any built-in.

>>> x = ['a', 'ab', 'abc', 'bc', 'c', 'ac']
>>> y = ['a', 'b']
>>> [r for r in x if not any(s in r for s in y)]
['c']

s in r does the partial match you want, for s in y checks all elements of y, and any is true if there was any match. Then we just invert it.

This is quadratic, O(len(x) * len(y)). If y is long, it may be more efficient to synthesize a regexp:

>>> import re
>>> yy = re.compile("|".join(re.escape(s) for s in y))
>>> [r for r in x if not yy.search(r)]
['c']

which should be merely O(len(x) + len(y)).