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)

Example

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

 
class Solution {
public:
    bool isMatch(const char *s, const char *p) {
       if (!*p) return !*s;
       if (*(p+1) != '*') return (*s == *p || (*s&&*p == '.')) && isMatch(s+1, p+1);
       while(*s == *p || (*s && *p == '.')) {
           if (isMatch(s, p+2)) return true;
           s++;
       }
       
       return isMatch(s, p+2);
    }
};

class Solution {
public:
    /**
     * @param s: A string 
     * @param p: A string includes "." and "*"
     * @return: A boolean
     */
     bool isMatch(const char *s, const char *p) {
       if (!*p) return !*s;
       int m = strlen(p);
       int n = strlen(s);
       
       vector<vector<bool>> match(m+1, vector<bool>(n+1, false));
       
       match[0][0] = 1;
       match[1][1] = s[0] == p[0] || p[0] == '.';
       
       // When s is empty, but p = '.*', p matches s
       for(int i = 2; i <=m; i++)
           match[i][0] = p[i-1] == '*'? match[i-2][0] : false;

       // starting from second char in p
       for(int i = 2; i <= m; i++) 
           for(int j = 1; j <= n; j++) 
              if (p[i-1]== '*') 
                match[i][j] = isSame(s[j-1], p[i-2])? match[i-2][j] || match[i-2][j-1] || match[i-1][j-1] || match[i][j-1] : match[i-2][j];
             else  
                match[i][j] = isSame(s[j-1], p[i-1]) && match[i-1][j-1];
           
        
        return match[m][n];
    }
    
    bool isSame(char a, char b){
        return (a == b || b=='.');
    }
};