Regex subsequence matching

Question

I'm using python but code in any language will do as well for this question.

Suppose I have 2 strings.

sequence ='abcd'
string = 'axyzbdclkd'

In the above example sequence is a subsequence of string

How can I check if sequence is a subsequence of string using regex? Also check the examples here for difference in subsequence and subarray and what I mean by subsequence.

The only think I could think of is this but it's far from what I want.

import re
c = re.compile('abcd')
c.match('axyzbdclkd')

Answer 1

Just allow arbitrary strings in between:

c = re.compile('.*a.*b.*c.*d.*')
# .* any character, zero or more times

Answer 2

You can, for an arbitrary sequence construct a regex like:

import re

sequence = 'abcd'
rgx = re.compile('.*'.join(re.escape(x) for x in sequence))

which will - for 'abcd' result in a regex 'a.*b.*c.*d'. You can then use re.find(..):

the_string = 'axyzbdclkd'
if rgx.search(the_string):
    # ... the sequence is a subsequence.
    pass

By using re.escape(..) you know for sure that for instance '.' in the original sequence will be translated to '\.' and thus not match any character.