class Solution:



    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        states = []
        state_i = 0
        for i in range(len(p)):
            if p[i] == "*":
                states[state_i-1] = (states[state_i0], '*')
            else:
                states.append(s[i], None)
                state_i += 1


        state_i = 0
        matches = False
        for c in s:
            curstate = states[states_i]
            if curstate[1] == c:
                if curstate[1] != "*":
                    state_i += 1

            else:
                if curstate[1] != "*":
                    state_i = 0
        return False