Untitled

class StateMachine:
    def __init__(self, transitions):
        self.transitions = {}
        for [fr, to, ev] in transitions:
            if fr not in self.transitions:
                self.transitions[fr] = {}
            self.transitions[fr][ev] = to

    def transit(self, s):
        state = 0
        for ch in s:
            if state not in self.transitions or (ch not in self.transitions[state] and '.' not in self.transitions[state]):
                return -1
            if ch not in self.transitions[state] and '.' in self.transitions[state]:
                state = self.transitions[state]['.']
            else:
                state = self.transitions[state][ch]
        return state


class Regex:
    def __init__(self, pattern):
        i = 0
        counter = 0
        transitions = []
        while i < len(pattern):
            if i == len(pattern) - 1:
                transitions.append([counter, counter + 1, pattern[i]])
                i, counter = i + 1, counter + 1
            elif pattern[i + 1] == '*':
                transitions.append([counter, counter, pattern[i]])
                i += 2
            else:
                transitions.append([counter, counter + 1, pattern[i]])
                i, counter = i + 1, counter + 1
        self.state_machine = StateMachine(transitions)
        self.end_state = counter

    def match(self, s):
        return self.state_machine.transit(s) == self.end_state


class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        regex = Regex(p)
        return regex.match(s)


if __name__ == '__main__':
    sln = Solution()
    print(sln.isMatch("aaa", "a*a"))