Pattern Matching

Challenge

Harder

Concepts

Algorithm Design

Download

pattern-match.zip

Solution

Pattern Matching: Solution

For a given pattern containing a and b placeholders, check to see if a provided string matches that pattern.

For example, the pattern aaba matches the string “foofoogofoo” (it can make “foo” into a and “go” into b). However, that same pattern, aaba, could not match “foofoofoodog”, since there are no values for a and b that could match that string and pattern (though we can find values for a and b for the pattern aaab for that string).

Patterns can only contain a and b and must start with a.

For example, we can do this for simple patterns containing only a’s:

>>> pattern_match("a", "foo")
True

>>> pattern_match("aa", "foofoo")
True

>>> pattern_match("aa", "foobar")
False

It’s possible for a to be zero-length (a=”“, b=”hi”):

>>> pattern_match("abbab", "hihihi")
True

Or b to be zero-length (a=”foo”, b=”“):

>>> pattern_match("aaba", "foofoofoo")
True

But, more typically, both are non-zero length:

>>> pattern_match("aa", "foodog")
False

>>> pattern_match("aaba" ,"foofoobarfoo")
True

Tricky, but works: (a=”foo”, b=”foobar”):

>>> pattern_match("aba" ,"foofoobarfoo")
True

We’ve given you a file, patternmatch.py with an empty pattern_match function (besides a sanity check on input):

def pattern_match(pattern, astring):
    """Can we make this pattern match this string?"""

    # Q&D sanity check on pattern

    assert (pattern.replace("a", "").replace("b", "") == ""
            and pattern.startswith("a")), "invalid pattern"

Implement this.

Hint