"""
正则匹配问题
"""
def is_match_on_iteration(s1, pattern):
    if not s1: return not pattern
    first_match = s1 and (pattern[0] in {s1[0], '.'})
    if len(pattern) >= 2 and pattern[1] == '*':
        return (is_match_on_iteration(s1, pattern[2:])  #一个也不匹配
                or
                is_match_on_iteration(s1[1:], pattern)  #匹配一个或多个
                )
    else:
        return first_match and is_match_on_iteration(s1[1:], pattern[1:])


def isMatch(text, pattern) -> bool:
    memo = dict() # 备忘录
    def dp(i, j):
        if (i, j) in memo: return memo[(i, j)]
        if j == len(pattern): return i == len(text)
        first = i < len(text) and pattern[j] in {text[i], '.'}
        if j <= len(pattern) - 2 and pattern[j + 1] == '*':
            ans = dp(i, j + 2) or first and dp(i + 1, j)
        else:
            ans = first and dp(i + 1, j + 1)
        memo[(i, j)] = ans
        return ans
    return dp(0, 0)