class R:
    def __init__(self, c):
        self.c = c
        self.is_star = False

    def match(self, c):
        return self.c == '.' or self.c == c


class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        rs = []
        """:type: list[R]"""

        for c in p:
            if c == '*':
                rs[-1].is_star = True
            else:
                rs.append(R(c))

        lr = len(rs)
        ls = len(s)
        s += '\0'

        dp = [[False] * (ls + 1) for _ in range(lr + 1)]
        dp[0][0] = True

        for i, r in enumerate(rs):
            for j in range(ls + 1):
                c = s[j - 1]

                if r.is_star:
                    dp[i + 1][j] = dp[i][j]

                    if j and r.match(c):
                        dp[i + 1][j] |= dp[i + 1][j - 1]
                else:
                    if j and r.match(c):
                        dp[i + 1][j] = dp[i][j - 1]
        return dp[-1][-1]
