O(n^2) solution based on building NFA


  • 0
    W

    Here is my O(n^2) solution based on building an NFA.

    class Solution(object):
    def buildNfa(self, p):
        nfa = [(False, [])]
        i = 0
        while i < len(p):
            value = p[i]
            if i + 1 < len(p) and p[i + 1] == '*':
                nfa[-1][1].extend([(len(nfa) - 1, value), (len(nfa), None)])
                nfa.append((False, []))
                i += 2
            else:
                nfa[-1][1].append((len(nfa), value))
                nfa.append((False, []))
                i += 1
        nfa[-1] = (True, nfa[-1][1])
        return nfa
    
    def closureAux(self, state, nfa, res):
        if state in res:
            return
        
        res.add(state)
        
        for nextState, value in nfa[state][1]:
            if value is not None:
                continue
            self.closureAux(nextState, nfa, res)
            
    def closure(self, states, nfa):
        addedStates = set()
        for state in states:
            self.closureAux(state, nfa, addedStates)
        states |= addedStates
        
    def transition(self, states, letter, nfa):
        newStates = set()
        for state in states:
            for nextState, value in nfa[state][1]:
                if value == '.' or value == letter:
                    newStates.add(nextState)
        self.closure(newStates, nfa)
        return newStates
        
    def matches(self, s, nfa):
        states = set()
        states.add(0)
        self.closure(states, nfa)
        
        for letter in s:
            states = self.transition(states, letter, nfa)
            if len(states) == 0:
                break
        
        for state in states:
            if nfa[state][0]:
                return True
        return False
        
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        nfa = self.buildNfa(p)
        return self.matches(s, nfa)

Log in to reply
 

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