is_match.py

#!/usr/bin/env python3

"""
Write a function that takes two strings as arguments, s and p,
and returns a boolean denoting whether s matches p.

p is a sequence of any number of the following:
1. a-z - which stands for itself
2. . - which matches any character
3. * - which matches 0 or more occurences of the previous single character

s = "aba", p = "ab" -> false
s = "aa", p = "a*" -> true
s = "ab", p = ".*" -> true
s = "ab", p = "." -> false
s = "aab", p = "c*a*b" -> true
s = "aaa", p = "a*." -> true
"""

def is_match(s: str, p: str) -> bool:
    """Checks whether s matches p.

    Here, p is a sequence of any number of the following:
    1. a-z - which stands for itself
    2. . - which matches any character
    3. * - which matches 0 or more occurences of the previous single character

    Args:
        s: any string
        p: a regex-like pattern
    
    Returns:
        A boolean denoting whether s matches p.

    """
    # pattern and string both empty: match
    if len(s) == 0 and len(p) == 0:
        return True
    
    # pattern empty but not string: no match
    if len(p) == 0:
        return False
    
    # 0+ occurences: 
    if len(p) >= 2 and p[1] == '*':
        # string empty but not pattern
        if len(s) == 0:
            return is_match(s, p[2:])
        # is_match(s, p[2:]): 0 occurences
        # is_match(s[1:], p): 1+ occurence
        return is_match(s, p[2:]) or is_match(s[1:], p)
    
    # string empty but not pattern: no match
    # (all following checks require 1+ characters in string)
    if len(s) == 0:
        return False

    # any character
    if p[0] == '.':
        return is_match(s[1:], p[1:])
    
    # specific character
    if s[0] == p[0]:
        return is_match(s[1:], p[1:])
    
    return False
    
def _test_is_match() -> None:
    assert(is_match('aba', 'ab') == False)
    assert(is_match('aa', 'a*') == True)
    assert(is_match('ab', '.*') == True)
    assert(is_match('ab', '.') == False)
    assert(is_match('aab', 'c*a*b') == True)
    assert(is_match('aaa', 'a*a') == True)

def main():
    _test_is_match()
    print('The is_match function passed all tests.')

if __name__ == '__main__':
    main()