6-liner in Python, beats 98.20%


  • 3
    class Solution(object):
        def isMatch(self, s, p, memo={("",""):True}):
            if not p and s:      return False
            if not s and p:      return set(p[1::2]) == {"*"} and not (len(p) % 2)
            if (s,p) in memo:    return memo[s,p]
            
            char, exp, prev = s[-1], p[-1], 0 if len(p) < 2 else p[-2]
            memo[s,p] =\
                   (exp == '*' and ((prev in {char, '.'} and self.isMatch(s[:-1], p, memo)) or self.isMatch(s, p[:-2], memo)))\
                   or\
                   (exp in {char, '.'} and self.isMatch(s[:-1], p[:-1], memo))
            return memo[s,p]
    
    # 445 / 445 test cases passed.
    # Status: Accepted
    # Runtime: 72 ms
    

  • 0
    C
    This post is deleted!

  • 0

    @catbaron- yes, to save space :D


  • 0
    C

    so beautiful solution


Log in to reply
 

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