Check if substring is in a list of strings?

by

Posted code

The OP’s posted code using any() is correct and should work. The spelling of “worldlist” needs to be fixed though.

Alternate approach with str.join()

That said, there is a simple and fast solution to be had by using the substring search on a single combined string:

>>> wordlist = ['yellow','orange','red']
>>> combined = '\t'.join(wordlist)

>>> 'or' in combined
True
>>> 'der' in combined
False

For short wordlists, this is several times faster than the approach using any.

And if the combined string can be precomputed before the search, the in-operator search will always beat the any approach even for large wordlists.

Alternate approach with sets

The O(n) search speed can be reduced to O(1) if a substring set is precomputed in advance and if we don’t mind using more memory.

Precomputed step:

from itertools import combinations

def substrings(word):
    for i, j in combinations(range(len(word) + 1), 2):
        yield word[i : j]

wordlist = ['yellow','orange','red']
word_set = set().union(*map(substrings, wordlist))

Fast O(1) search step:

>>> 'or' in word_set
True
>>> 'der' in word_set
False

Leave a Comment