AC Python recursive solution


  • 0
    Y
    class Solution(object):
        def isMatch(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: bool
            """
            return self.rec(s, p)
            
        def rec(self, s, p):
            if not p and not s:
                return True
            elif len(p) > 1 and p[1] == '*': 
                # used to avoid LTE cases like a*a*a*a*a*a*a*a*a*
                if len(p) > 3 and p[3] == '*' and p[2] == p[0]:
                    return self.rec(s, p[2:])
                ##########################
                c = p[0]
                if c == '.':
                    for i in xrange(len(s)+1):
                        if self.rec(s[i:], p[2:]):
                            return True
                else:
                    for i in xrange(len(s)+1):
                        if self.rec(s, c*i+p[2:]):
                            return True
            elif p and s and (p[0] == '.' or p[0] == s[0]):
                return self.rec(s[1:], p[1:])
            return False
    

Log in to reply
 

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