recursive solution in Python 132ms


  • 0
    A
    class Solution(object):
        def isMatch(self, s, p):
            self.p_original = p
            self.s_original = s
            return self._isMatch(s, p)
    
        def _isMatch(self,s, p, star = -1, ss = 0):
            ls = len(s)
            lp = len(p)
    
            if lp == 0:
                if ls == 0:
                    return True
                if not star == -1:
                    ss += 1
                    return self._isMatch(self.s_original[ss:],self.p_original[star+1:],star,ss)
                return False
    
            c = p[0]
            if c == '?':
                return ls > 0 and self._isMatch(s[1:],p[1:],star,ss)
            if c == '*':
                t = 1
                while t < lp and p[t] == '*':
                    t+=1
                p = p[t-1:]
                return self._isMatch(s,p[1:],len(self.p_original)-len(p),len(self.s_original)-len(s))
    
            if ls == 0:
                return False
            if s[0] == p[0]:
                return self._isMatch(s[1:],p[1:],star,ss)
            if not star == -1:
                ss += 1
                return self._isMatch(self.s_original[ss:],self.p_original[star+1:],star,ss)
            return False
    

Log in to reply
 

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