I cheat in this question,haha


  • -3
    Z

    I split the p by '*', and then find every split

    I solve this by python with some ugly coding (it can be more pythonic), but it run well in 120ms which is almost the fastest in python solution

    I think this solution may be somekind of cheat

    ##AC
    import re
    class Solution:
        # @param {string} s
        # @param {string} p
        # @return {boolean}
        def isMatch(self, s, p):
            if p == s:
                return True
            if not p:
                return False
            p = p.replace('?','.')
            ##split p by '*'
            plist = p.split('*')
            begin = 0
            for i,psplit in enumerate(plist):
                if '.' in psplit:
                    ##last one
                    if i == len(plist)-1:
                        begin = self.regularMatch(s,psplit,begin,1)
                        if p[-1]!='*' and begin+len(psplit) !=len(s):
                            return False
                    else:
                        begin = self.regularMatch(s,psplit,begin,0)
                    if begin == -1:
                        return False
                    ## first one
                    if i==0 and p[0] != '*' and begin!= 0:
                        return False
                    begin += len(psplit)
                else:
                    ##last one
                    if i == len(plist)-1:
                        lb = s.rfind(psplit)
                        if lb < begin:
                            return False
                        else:
                            begin = lb
                            if p[-1]!='*' and begin+len(psplit) !=len(s):
                                return False
                    else:
                        begin = s.find(psplit,begin)
                    if begin == -1:
                        return False
                    ##first one
                    if i==0 and p[0] != '*' and begin!= 0:
                        return False
                    begin += len(psplit)
            return True
                
        def regularMatch(self, s, p,begin,islast):
                pattern = re.compile(p)
                result = pattern.search(s,begin)
                if not result:
                    return -1
                if not islast:
                    return result.start()
                if islast:
                    while result:
                        begin = result.start()
                        result = pattern.search(s,begin+1)
                    return begin

  • 0
    T

    It's interesting that the regex engine can't handle these...

    import re
    class Solution:
    	def isMatch(self, s, p):
    		p = re.sub('\*+', '*', p); # collapse *s
    		p = p.replace('?','.').replace('*','.*') # regexify
    		return re.match(p, s);
    

    It TLEs on many too many stars, when s doesn't match p.


Log in to reply
 

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