# Solved by NFA

• ``````__author__ = 'blog.fucus.me'

class Digraph:
def __init__(self, N):
self.link = [[False for _ in range(N)] for _ in range(N)]

def dfs(self, starts):
reached = set()
if type(starts) is list:
stack = starts
else:
stack = [starts, ]
while len(stack) > 0:
v = stack.pop()
if v not in reached:
if reach and i != v:
stack.append(i)
return reached

# modified from book:Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne, Charpter 5.4
class NFA:
def __init__(self, re):
M = len(re)
G = Digraph(M+1)
ops = []
for i in range(M):
lp = i
if re[i] == '(' or re[i] == '|':
ops.append(i)
elif re[i] == ')':
top = ops.pop()
if re[top] == '|':
lp = ops.pop()
else:
lp = top
if i < M - 1 and re[i+1] == '*':

if i < M - 1 and re[i+1] == '?':

direct_symbol = set(['(', '*', ')', '?'])
if re[i] in direct_symbol:
self.G = G
self.M = M
self.re = re
def recognize(self, txt):
pc = self.G.dfs(0)
for t in txt:
match = list()
for v in pc:
if v < self.M:
if (self.re[v] == t) or self.re[v] == '.':
match.append(v+1)
pc = self.G.dfs(match)
return self.M in pc

class Solution(object):
def isMatch(self, s, p):
nfa = NFA(p)
return nfa.recognize(s)

``````

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