solved by NFA


  • 0
    F
    __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] == '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)))
    
    

Log in to reply
 

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