Untitled
python
a month ago
2.1 kB
2
Indexable
Never
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)