Untitled

mail@pastecode.io avatar
unknown
python
a year ago
2.1 kB
3
Indexable
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]:
                return 0
            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] == '.':
                """
                All characters possible to make transition
                .b
                0 - a - 1
                0 - b - 1
                ....
                0 - z - 1
                1 - b - 2
                """
                for ch in range(26):
                    transitions.append([counter, counter + 1, chr(ch + ord('a'))])
                i += 1
            elif pattern[i + 1] == '*':
                """
                ab*c
                0 - a - 1
                1 - b - 1
                1 - c - 2
                """
                transitions.append([counter, counter, pattern[i]])
                if i + 2 < len(pattern):
                    transitions.append([counter, counter + 1, pattern[i + 2]])
                i += 2
            else:
                transitions.append([counter, counter + 1, pattern[i]])
                i += 1
            counter += 1
        print(transitions)
        self.state_machine = StateMachine(transitions)
        self.end_state = counter - 1
    
    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)