# Python Greedy Solution (passes and beats 79.91%)

• 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 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
``````

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