Description

Implement regular expression matching with support for '.' and '*'.

• '.' Matches any single character.
• '*' Matches zero or more of the preceding element.
  The matching should cover the entire input string (not partial).

The function prototype should be:

bool isMatch(string s, string p)

Solution

与192的区别，这里的*始终与前面一个字符进行绑定

class Solution:
    """
    @param s: A string 
    @param p: A string includes "." and "*"
    @return: A boolean
    """
    def is_empty(self,p):
        if len(p) % 2 == 1:
            return False
        
        for i in range(len(p) // 2):
            if p[i * 2 + 1] != '*':
                return False
        return True
    def match_char(self,s,i,p,j):
        if (i,j) in self.memo:
            return self.memo[(i,j)]
        
        if i == len(s):
           return self.is_empty(p[j:])
        if j == len(p):
            return False
        
        if j+1 < len(p) and p[j+1] =='*':
            # 注意此处要考虑”.“
            self.memo[(i,j)] = self.match_char(s,i,p,j+2)
            if s[i] == p[j] or p[j]=='.':
                self.memo[(i,j)] = self.memo[(i,j)] or self.match_char(s,i+1,p,j)
                
        elif p[j] == '.':
            self.memo[(i,j)] = self.match_char(s,i+1,p,j+1)
        else:
            if s[i]==p[j]:
                self.memo[(i,j)] = self.match_char(s,i+1,p,j+1)
            else:
                return False
        return self.memo[(i,j)]
    def isMatch(self, s, p):
        self.memo = dict()
        return self.match_char(s,0,p,0)