# Python Solution, very clear with several helper functions

• Step 1: In p, replace consecutive * with a single *

Step 2: eliminate prefix and suffix of p and s, without touching * in p. Now p should either be trivial, or starts and ends with *

Step 3: get first substring (called firstGroup) in p without a *. Then try find the first occurrence of firstGroup in s. If no occurrence, match fails.

Step 4: In p, remove leading * and firstGroup. In s, remove corresponding leading substring. Go back to step 3.

Step 5: If match never failed, and we finally make p=='*', we find a global match.

``````class Solution(object):

def removeConsecutiveStars( self, p ):
"""
shrink consecutive *s into a single *
returns the result string
"""
while "**" in p:
p = p.replace( "**", "*", 100 )
return p

def removeCommonPrefix( self, s, p ):
"""
remove Common Prefix in s and p. '?' in p can match anything in s
"""
sB,pB = 0,0
while sB<len(s) and pB<len(p) and p[pB]!='*' and ( p[pB]=='?' or p[pB]==s[sB] ):
pB += 1
sB += 1
return ( s[sB:], p[pB:] )

def removeCommonSuffix( self, s, p ):
"""
remove Common Suffix in s and p. '?' in p can match anything in s
"""
s,p = s[::-1],p[::-1]
(s,p) = self.removeCommonPrefix(s,p)
return (s[::-1],p[::-1])

def getFirstGroup( self, p ):
"""
In p, find substring between first and second *
"""
secondStar = p.find( '*', 1 )

if p[0] != '*': raise Exception( 'Sanity check failed in getFirstGroup' )
if secondStar == -1: raise Exception( 'Sanity check failed in getFirstGroup' )

return p[ 1 : secondStar ]

def findGroup( self, s, group ):
"""
find the first occurence of group in s
return ret means s[ ret : ret+len(group) ] == group. If fails, return -1
"""
for beginI in range(len(s)-len(group)+1):
for i in range(len(group)):
if group[i]!='?' and group[i] != s[beginI+i] :
break
else: # did not break, meaning we have a perfect match
return beginI

return -1

def isMatch(self, s, p ):
"""
:type s: str
:type p: str
:rtype: bool
"""

# remove repeating *, remove common prefix and suffix
p = self.removeConsecutiveStars( p )
s,p = self.removeCommonPrefix( s, p )
s,p = self.removeCommonSuffix( s, p )

# Case 1: p has no *
if len(p)==0:
return len(s)==0

# Case 2: result p has leading or trailing non-* char, which should match char in s but did not
if len(p) and ( p[0]!='*' or p[-1]!='*' ):
return False

# Case 3: result p starts with * and ends with *
while len(p) > 1:
# split p by '*'. Get the first group, and try match it in s
firstGroup = self.getFirstGroup( p )
groupLocation = self.findGroup( s, firstGroup )

if groupLocation==-1: # no match in s
return False

# matched first group in s, remove them in s and p
s = s[ groupLocation + len(firstGroup) : ]
p = p[ 1 + len(firstGroup) : ]

# now p == '*'
return True``````

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