A Python state machine style (NFA) solution


  • 0
    S

    After failed a lot of times trying to cover all found corner cases, I tried this state machine like solution at the first time. Hope this share can help.
    There are many corner cases, even using the state machine.
    My solution follows an interesting paper using NFA to solve regular expression problem. It is post here. https://swtch.com/~rsc/regexp/regexp1.html It's well written, easy to understand.

    My code is not optimized enough. Will do that later :). But hope this can explain the idea at least.
    Basic Idea:

    1. Each character in the pattern p can be taken as an input for a state. A state changes to others after receiving the input.
    2. Build a series of state and connect them into a state machine. Give the string s to the machine, and see the result.

    Code:

    class State:
    
        def __init__(self, value):
            self.val = value
            self.next = []
    
    
    class Solution:
    
        def isMatch(self, s, p):
    
            # Solution: build a state machine first, and match the string
            # recursively.
    
            def build(p):
                if not p:
                    return None
                stack = []
                for i, e in enumerate(p):
                    # add e
                    if e != '*':
                        state = State(e)
                        if stack:
                            stack[-1].next.append(state)
                        stack.append(state)
                    else:  # add *
                        state = State(None)
                        if len(stack) > 1:
                            stack[-1].next.append(state)
                            state.next.append(stack[-1])
                            stack[-2].next.remove(stack[-1])
                            stack[-2].next.append(state)
                            stack[-1] = state
                        elif len(stack) == 1:
                            stack[0].next.append(state)
                            state.next.append(stack[0])
                            stack[0] = state
                        else:
                            state.next.append(state)
                            stack.append(state)
    
                stack[-1].next.append(None)  # final state
    
                return stack[0]
    
            def match(s, p):
                # if dead loop, return False
                if (s, p) in states:
                    return False
                states.add((s, p))
                # if read end return judgement
                if not p:
                    if not s:
                        return True
                    return False
    
                if p.val == None:
                    return any([match(s, np) for np in p.next])
    
                subs = s[:len(p.val)]
                if comp(subs, p.val):
                    return any([match(s[len(p.val):], np) for np in p.next])
    
                return False
    
            def comp(s, p):  # support only char and .
                # print s, p
                if len(s) != len(p):
                    return False
                for i, c in enumerate(s):
                    if c != p[i] and p[i] != '.':
                        return False
                return True
    
            head = build(p)
            if s and not head:
                return False
            states = set()
            ans = match(s, head)
            return ans

Log in to reply
 

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