My Python solution


  • 0
    Y

    Simulated a restricted version of nfa

    class Solution:
        # @return a boolean
        def isMatch(self, s, p):
            reg = []
            for c in p:
                if c == "*":
                    reg[-1] = reg[-1]+c
                else:
                    reg.append(c)
            accept = len(reg)
            reg.append("")
            #print(reg)
    
            cur = [0]
            for i in range(len(reg)):
                if len(reg[i]) <= 1:
                    break
                else:  # reg[i][1] == "*":
                    cur.append(i+1)
    
            for char in s:
                #print(cur)
                #print("checkchar: "+char)
                next_states = []
                for i in cur:
                    #print("checkreg: "+str(reg[i]))
                    if reg[i] and (reg[i][0] == char or reg[i][0] == "."):
                        next_states.append(i+1)
                        for x in range(i+1, len(reg)):
                            if len(reg[x]) <= 1:
                                break
                            else:  # reg[x][1] == "*":
                                next_states.append(x+1)
                    # previous star
                    if i>0 and len(reg[i-1])>1 and (reg[i-1][0] == char or reg[i-1][0] == "."):
                        next_states.append(i)
                        for x in range(i, len(reg)):
                            if len(reg[x]) <= 1:
                                break
                            else:  # reg[x][1] == "*":
                                next_states.append(x+1)
                    #print("next_states: "+str(next_states))
                next_states = list(set(next_states))
    
                if not next_states:
                    #print("no next_states")
                    return False
    
                cur = next_states
    
            if accept in cur:
                    #print("accepted")
                    return True
            return False

Log in to reply
 

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