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)