An Unclear Python Solution Using Brute-Force Search


  • 0
    C
    def isMatch(self, s, p):
        def find_district(j, pats):
            found = True
            for ps in pats:                    
                l = len(ps)
                if s[j:j+l] == ps: # s[x:x]=='' is True
                    j += l+1
                else:
                    found = False
                    break
            if found:
                return j-1
            else:
                return None
        
        def find(i, pat):
            pats = pat.split('?')
            while i<=len(s)-len(pat):
                r = find_district(i, pats)
                if r:
                    return r
                else:
                    i += 1
            return None
    
        patsplit = p.split('*')
        if len(patsplit) == 1:
            return find_district(0, patsplit[0].split('?')) == len(s)
        patsplit = filter(lambda x:x != '', patsplit)
        if len(patsplit) == 0:
            return True
        
        # deal with head
        if p[0] != '*':
            head = find_district(0, patsplit[0].split('?'))
            if not head:
                return False
            patsplit = patsplit[1:]
        else:
            head = 0
    
        # deal with tail
        if p[-1] != '*':
            tail = len(s)-len(patsplit[-1])
            if tail < head or not find_district(tail, patsplit[-1].split('?')):
                return False
            if patsplit:
                patsplit.pop()
        else:
            tail = len(s)
        
        # deal with mid
        i = head
        for pat in patsplit:
            i = find(i, pat)
            if not i:
                return False
                
        return i <= tail

Log in to reply
 

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