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
Solution1: standard DP
class Solution:
# @return a boolean
def isMatch(self, s, p):
opt = [[False]*(len(p)+1) for x in range(len(s)+1)]
# base case
opt[0][0] = True
for j in xrange(1,len(p),2):
if p[j] == '*':
opt[0][j+1] = True
else:
break
# iteration
for i in xrange(1,len(s)+1):
for j in xrange(1,len(p)+1):
if s[i-1] == p[j-1] or p[j-1] == '.':
opt[i][j] = opt[i-1][j-1]
elif p[j-1] == '*':
opt[i][j] = opt[i][j-2] or ((s[i-1] == p[j-2] or p[j-2] == '.') and opt[i-1][j])
return opt[len(s)][len(p)]
