# O(n^2) solution based on building NFA

• Here is my O(n^2) solution based on building an NFA.

``````class Solution(object):
def buildNfa(self, p):
nfa = [(False, [])]
i = 0
while i < len(p):
value = p[i]
if i + 1 < len(p) and p[i + 1] == '*':
nfa[-1][1].extend([(len(nfa) - 1, value), (len(nfa), None)])
nfa.append((False, []))
i += 2
else:
nfa[-1][1].append((len(nfa), value))
nfa.append((False, []))
i += 1
nfa[-1] = (True, nfa[-1][1])
return nfa

def closureAux(self, state, nfa, res):
if state in res:
return

for nextState, value in nfa[state][1]:
if value is not None:
continue
self.closureAux(nextState, nfa, res)

def closure(self, states, nfa):
for state in states:

def transition(self, states, letter, nfa):
newStates = set()
for state in states:
for nextState, value in nfa[state][1]:
if value == '.' or value == letter:
self.closure(newStates, nfa)
return newStates

def matches(self, s, nfa):
states = set()
self.closure(states, nfa)

for letter in s:
states = self.transition(states, letter, nfa)
if len(states) == 0:
break

for state in states:
if nfa[state][0]:
return True
return False

def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
nfa = self.buildNfa(p)
return self.matches(s, nfa)``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.