Algorithm to match 2 lists with wildcards

Question

I'm looking for an efficient way to match 2 lists, one wich contains complete information, and one which contains wildcards. I've been able to do this with wildcards of fixed lengths, but am now trying to do it with wildcards of variable lengths.

Thus:

match( ['A', 'B', '*', 'D'], ['A', 'B', 'C', 'C', 'C', 'D'] )

would return True as long as all the elements are in the same order in both lists.

I'm working with lists of objects, but used strings above for simplicity.

Answer 1

[edited to justify no RE after OP comment on comparing objects]

It appears you are not using strings, but rather comparing objects. I am therefore giving an explicit algorithm — regular expressions provide a good solution tailored for strings, don't get me wrong, but from what you say as a comment to your questions, it seems an explicit, simple algorithm may make things easier for you.

It turns out that this can be solved with a much simpler algorithm than this previous answer:

def matcher (l1, l2):
    if (l1 == []):
        return (l2 == [] or l2 == ['*'])
    if (l2 == [] or l2[0] == '*'):
        return matcher(l2, l1)
    if (l1[0] == '*'):
        return (matcher(l1, l2[1:]) or matcher(l1[1:], l2))
    if (l1[0] == l2[0]):
        return matcher(l1[1:], l2[1:])
    else:
        return False

The key idea is that when you encounter a wildcard, you can explore two options :

• either advance in the list that contains the wildcard (and consider the wildcard matched whatever there was until now)
• or advance in the list that doesn't contain the wildcard (and consider that whatever is at the head of the list has to be matched by the wildcard).