```
__author__ = 'blog.fucus.me'
class Digraph:
def __init__(self, N):
self.link = [[False for _ in range(N)] for _ in range(N)]
def addEdge(self, out, to):
self.link[out][to] = True
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:
reached.add(v)
for i, reach in enumerate(self.link[v]):
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()
G.addEdge(lp, top+1)
G.addEdge(top, i)
else:
lp = top
# look ahead
if i < M - 1 and re[i+1] == '*':
G.addEdge(lp, i+1)
G.addEdge(i+1, lp)
if i < M - 1 and re[i+1] == '?':
G.addEdge(lp, i+1)
direct_symbol = set(['(', '*', ')', '?'])
if re[i] in direct_symbol:
G.addEdge(i, i+1)
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)
```