# A Python state machine style (NFA) solution

• After failed a lot of times trying to cover all found corner cases, I tried this state machine like solution at the first time. Hope this share can help.
There are many corner cases, even using the state machine.
My solution follows an interesting paper using NFA to solve regular expression problem. It is post here. https://swtch.com/~rsc/regexp/regexp1.html It's well written, easy to understand.

My code is not optimized enough. Will do that later :). But hope this can explain the idea at least.
Basic Idea:

1. Each character in the pattern p can be taken as an input for a state. A state changes to others after receiving the input.
2. Build a series of state and connect them into a state machine. Give the string s to the machine, and see the result.

Code:

``````class State:

def __init__(self, value):
self.val = value
self.next = []

class Solution:

def isMatch(self, s, p):

# Solution: build a state machine first, and match the string
# recursively.

def build(p):
if not p:
return None
stack = []
for i, e in enumerate(p):
if e != '*':
state = State(e)
if stack:
stack[-1].next.append(state)
stack.append(state)
state = State(None)
if len(stack) > 1:
stack[-1].next.append(state)
state.next.append(stack[-1])
stack[-2].next.remove(stack[-1])
stack[-2].next.append(state)
stack[-1] = state
elif len(stack) == 1:
stack[0].next.append(state)
state.next.append(stack[0])
stack[0] = state
else:
state.next.append(state)
stack.append(state)

stack[-1].next.append(None)  # final state

return stack[0]

def match(s, p):
# if dead loop, return False
if (s, p) in states:
return False
# if read end return judgement
if not p:
if not s:
return True
return False

if p.val == None:
return any([match(s, np) for np in p.next])

subs = s[:len(p.val)]
if comp(subs, p.val):
return any([match(s[len(p.val):], np) for np in p.next])

return False

def comp(s, p):  # support only char and .
# print s, p
if len(s) != len(p):
return False
for i, c in enumerate(s):
if c != p[i] and p[i] != '.':
return False
return True