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(const char *s, const char *p)Some examples:isMatch("aa","a") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "a*") → trueisMatch("aa", ".*") → trueisMatch("ab", ".*") → trueisMatch("aab", "c*a*b") → trueUse DP to solve this problem code is as followclass Solution:# @return a boolean## have an n*m boolean array## compare with '.' '*' and general case## return dp[-1][-1]def isMatch(self, s, p):dp = [[False for j in range(len(p) + 1)] for i in range(len(s) + 1)]dp[0][0] = Truefor j in range(1,len(p) + 1):if p[j-1] == '*':if j >= 2:dp[0][j] = dp[0][j – 2]for i in range(1, len(s) + 1):for j in range(1, len(p) + 1):if p[j – 1] == '.': ## first casedp[i][j] = dp[i – 1][j – 1]elif p[j – 1] == '*':#aa *a case#.* casedp[i][j] = dp[i][j – 1] or dp[i][j – 2] or (dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.'))else:dp[i][j] = s[i-1] == p[j-1] and dp[i – 1][j – 1]return dp[-1][-1]
，每年的情人节圣诞节除夕，也和他共度。甚至连吵架也是重复的，
