-1
$\begingroup$

If you are given a pattern and a string, check recursively if the string fits in the pattern. The given pattern will be like "dooo?g*a". A question mark can be replaced with one character and asterisk can be replaced with multiple characters. Other characters have to match. Help me with the asterisk part.

def fit_pattern(pattern,string):
    if string == pattern:
        return True
    if pattern[0] == "?" or string[0] == pattern[0]:
        return fit_pattern(pattern[1:], string[1:])
    return False
$\endgroup$
0
$\begingroup$

Something like...

def fits(pattern, string):
    if len(pattern) == 0:
        return (len(string) == 0)

    if pattern[0] == "*":
        if len(string) == 0:
            return fits(pattern[1:], string)
        return (fits(pattern, string[1:]) or fits(pattern[1:], string))

    if len(string) == 0:
        return False

    if pattern[0] == "?":
        return fits(pattern[1:], string[1:])

    return ((pattern[0] == string[0]) and fits(pattern[1:], string[1:]))

Explanation:

  1. An empty string for the pattern matches only the empty string.
  2. A pattern starting with an asterisk matches the empty string only if the rest of the pattern matches the empty string (i.e., it's empty or consists of asterisks).
  3. A pattern starting with an asterisk matches an arbitrary string if either (or both) of two conditions hold: either the pattern matches the rest of the string after the asterisk consumes the first character, or the rest of the pattern matches the string (in which case the asterisk consumes nothing).
  4. Any non-empty pattern starting with something other than an asterisk cannot possibly match the empty string.
  5. If the pattern starts with a question mark, the pattern matches a string if the rest of the pattern matches the string after the first character.
  6. In all other cases (not asterisks or question marks), the pattern matches the string if the first characters match and if the rest of the pattern matches the rest of the string.

I suspect the part you're most interested in is the following insight: *x matches ay if and only if (*x matches y OR x matches ay).

Exercise: how would you change this code so that * has to match at least one character?

$\endgroup$

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.