Python Solution, very clear with several helper functions


  • 0
    C

    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

Log in to reply
 

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