Regular Expression Matching

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)]