Python solution with detailed explanation


  • 0
    G

    Solution

    Regular Expression Matching https://leetcode.com/problems/regular-expression-matching/

    Algorithm

    • Similar idea like https://leetcode.com/problems/wildcard-matching/, except we need to proactively scan the next character and if it " * ", then take we can either accept or reject.
    • Tricky boundary condition is "", "a*" or "", ".*c*". We need to check: i == len(s) and p[j:].count('*')*2 == len(p[j:])
    from collections import defaultdict   
    class Solution(object):
        def helper(self, i, j, s, p, cache):
            if i == len(s) and j == len(p):
                return True
            elif i == len(s) and p[j:].count('*')*2 == len(p[j:]):
                return True
            elif i == len(s) or j == len(p):
                return False
            elif i in cache and j in cache[i]:
                return cache[i][j]
            else:
                if j+1 != len(p) and p[j+1] == "*" and p[j] != ".":
                    x1 = ((s[i] == p[j]) and self.helper(i+1, j, s, p, cache))
                    cache[i][j] = x1 or self.helper(i, j+2, s, p, cache)
                elif j+1 != len(p) and p[j+1] == "*" and p[j] == ".":
                    cache[i][j] = self.helper(i, j+2, s, p, cache) or self.helper(i+1, j, s, p, cache)
                elif p[j] == "." or s[i] == p[j]:
                    cache[i][j] = self.helper(i+1, j+1, s, p, cache)
                else:
                    cache[i][j] = False
                return cache[i][j]
    
        def isMatch(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: bool
            """
            return self.helper(0, 0, s, p, defaultdict(dict))        
    

Log in to reply
 

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