0
\$\begingroup\$

I want to find if all of a list of substrings exist in a string, in the correct order (with or without spaces between them), it seems to be a good use for regex.

I think I need to build a regex filter of "a.*b.*c" and use search to find that anywhere in my string.

Are there any other approaches I could consider or built in functions that might do this for me?

from re import search

def are_substrings_in_text(substrings,text):
    
    return search("".join([s+".*" for s in substrings]),text) is not None                  

print(are_substrings_in_text(["a","b","c"],"abacus")) # >True
print(are_substrings_in_text(["a","c","b"],"abacus")) # >False
print(are_substrings_in_text(["a","c","z"],"abacus")) # >False
\$\endgroup\$
4
\$\begingroup\$

The problem with your current approach is that it can give incorrect results or raise an exception if any of the substrings contain characters that have special meaning in Python regular expressions.

are_substrings_in_text(['a', '.', 's'], 'abacus'))   # Returns True
are_substrings_in_text(['a', '+', 's'], 'abacus'))   # Raises exception

The solution is to escape such characters so that they are handled as literal substrings. This illustration also makes a few cosmetic adjustments to simplify things for readability:

from re import search, escape

def are_substrings_in_text(substrings, text):
    pattern = '.*'.join(escape(s) for s in substrings)
    return bool(search(pattern, text))
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Any reason you're not using '.*'.join(escape(s) for s in substrings)? \$\endgroup\$
    – AJNeufeld
    Dec 1 '21 at 23:21
  • 1
    \$\begingroup\$ @AJNeufeld I blame my aging mind. \$\endgroup\$
    – FMc
    Dec 1 '21 at 23:51
3
\$\begingroup\$

It isn't necessary to use regular expressions (the re module), use the str.index() method. For the examples given, re.search takes 3x longer.

def are_substrings_in_text_index(substrings, text):
    start = 0
    try:
        for substring in substrings:
            start = text.index(substring, start) + len(substring)
            
        return True
    
    except ValueError:
        return False
\$\endgroup\$
1
  • \$\begingroup\$ Good point on the performance, thanks! It seems to vary depending on the relationship between the number of substrings and the length of the text; I guess in a real scenario one would model it with realistic data to see the best approach, If it was really time critical. I also noticed that "if substring not in text" is significantly faster than either; and regex REALLY struggles with near-misses. So a filter pass to see if at least each character exists in the text will speed up finding non-matches massively too. \$\endgroup\$
    – JeffUK
    Dec 2 '21 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.