Python Greedy Solution (passes and beats 79.91%)


  • 0
    M

    The key in this algorithm (not particularly innovative but at least I came up with it on my own) is that greedy approach can be used once we split (as in Pythonic language) the pattern with asterisk:

    e.g. for " abbbcca " with " *a*b?c* ", we can find the 1st instance of " a ", then the 1st instance of " b?c " , etc.

    Extra handling needs to be done if asterisks aren't at the beginning or end.

    I'm pretty sure that this algorithm can still be optimized, what do you think?

    class Solution(object):
        def isMatch(self, s, p):
            def helper(ss,pp,rv): # compares 2 strings of equal length
                return rv if all (n=='?' or m==n for m,n in zip(ss,pp)) else -1
    
            def patternMatch(S,P,ph,pt): # matches 2 un-truncated strings and returns the earliest occurrence if any
                if len(S)<len(P):
                    return -1
                if ph and pt: #match from head to tail
                    return 0 if len(S)==len(P) and helper(S,P,0)!=-1 else -1
                if ph: # match from head
                    return helper(S[:len(P)],P,0)
                if pt: # match from tail
                    return helper(S[-len(P):],P,len(S)-len(P))
                for x in range(0,len(S)-len(P)+1): # loose ends -> brute-force
                    if helper(S[x:x+len(P)],P,x)!=-1:
                        return x
                return -1
            
            if not p: #p is empty
                return not s # true iff s is also empty
            if all (ch=='*' for ch in p): #p is all stars
                return True # true for any string
            if not s: #s is empty
                return False # p isn't empty or all stars
    
            phead,ptail = map(lambda x: x!='*', (p[0], p[-1]))
            p2=[x for x in p.split("*") if x] # generate list of patterns and eliminate redundant *s
            i,j,ip,jp=0,len(p2)-1,0,len(s)
    
            if phead and ptail and not j: # if there's only 1 element and it needs to be matched both from beginning to end (e.g. "l?ee??t")
                return True if patternMatch(s,p,True,True)!=-1 else False
    
            if phead: # match from head
                if patternMatch(s[ip:jp],p2[i],True,False) == -1:
                    return False
                i,ip=i+1,ip+len(p2[i])
            if i>j:
                return True
                
            if ptail: # match from tail
                if patternMatch(s[ip:jp],p2[j],False,True) == -1:
                    return False
                j,jp=j-1,jp-len(p2[j])
            
            while i<=j: # all patterns have loose ends
                t = patternMatch(s[ip:jp],p2[i],False,False)
                if t == -1:
                    return False
                i,ip=i+1,ip+len(p2[i])+t
            return True
    

Log in to reply
 

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