class Solution(object):

    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        self.memo = dict()
        return self.isMatch2(s,p,0,0)

    def isMatch2(self, s, p, sindex, pindex):
        # Base cases
        #print(s[sindex:],p[pindex:])
        if (sindex, pindex) in self.memo:
            return self.memo[sindex,pindex]

        if len(p) == pindex:
            rval = len(s) == sindex
            self.memo[sindex,pindex] = rval
            return rval

        first_match = sindex < len(s) and p[pindex] in [s[sindex], '.']

        #continuing cases
        if pindex < len(p) - 1 and p[pindex + 1] == '*':
            # first see if not-matching the starred character is possible
            if self.isMatch2(s, p, sindex, pindex + 2):
                self.memo[sindex, pindex] = True
                return True
            else:
                rval = first_match and self.isMatch2(s,p, sindex + 1, pindex)
                self.memo[sindex, pindex] = rval
                return rval
        else:
            rval = first_match and self.isMatch2(s,p, sindex + 1, pindex + 1)
            self.memo[sindex,pindex]  = rval
            return rval