# 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] == 'd' and t.isdigit()):
match.append(v+1)
pc = self.G.dfs(match)
return self.M in pc

class Solution(object):
def isNumber(self, s):
exp_num = '(-|+)?((dd*(.d*)?)|(.dd*))(e(-|+)?dd*)?'
s = s.strip()
nfa = NFA(exp_num)
return nfa.recognize(s)

if __name__ == '__main__':
t_case = ['1. ', ' 1.12', '.1', '1e-10']
f_case = ['.', 'e9', ' ', '. 1', 'aafd']
for c in t_case:
print('"%s" is number,result:%s'
% (c, Solution().isNumber(c)))
for c in f_case:
print('"%s" is not number,result:%s'
% (c, Solution().isNumber(c)))

``````

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