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") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
My Solution:
class Solution:
def isEqual(self,a,b):
if a=="." or b==".":
return True
else:
return True if a==b else False
def isMatch(self,S,P):
N=len(S)
M=len(P)
S+="?"
P+="?"
DP=[[False for i in range(M+1)]for j in range(N+1)]
DP[N][M]=True
for j in range(M-1,-1,-1):#Pattern
for i in range(N,-1,-1):#String
if P[j]=="*":
continue
if P[j+1]!="*":
if self.isEqual(P[j],S[i]):
if i<N:
DP[i][j]=DP[i+1][j+1]
else:
if DP[i][j+2]:
DP[i][j]=True
continue
cnt=0
while 1:
if i+cnt+1>N:
break
if not self.isEqual(S[i+cnt],P[j]):
break
if DP[i+1+cnt][j+2]==True:
DP[i][j]=True
break
cnt+=1
return DP[0][0]