Regular Expression Matching

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

------------------- thinking ----------------------------
this problem is quite different from wildcard matching problem!!!! isMatch("aab", "c*a*b") → true
https://leetcode.com/discuss/26809/dp-java-solution-detail-explanation-from-2d-space-to-1d-space
https://leetcode.com/discuss/27140/three-solutions-for-this-question
------------------- codes -------------------------------
class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        // get len(s) and make sure len(s) >= len(p) - count(p, '*')
        int slen = 0;
        int plen = 0;
        for (auto q1 = s; *q1 != '\0'; q1++) {
            slen++;
        }
        int star_cnt = 0;
        for (auto q1 = p; *q1 != '\0'; q1++) {
            plen++;
        }
        bool dp[slen+1][plen+1];
        dp[0][0] = true;
        for (int j = 1; j <= plen; j++) {
            //bug here
            dp[0][j] = j > 1 && dp[0][j - 2] && (p[j-1] == '*');
        }
        for (int i = 1; i <= slen; i++) {
            dp[i][0] = false;
            for (int j = 1; j <= plen; j++) {
                if (p[j-1] == '*') {
                    if (j == 1) {
                        dp[i][j] = false;
                    } else {
                        //bug here !!! should be comparing with one character before p[j-1]
                        if (s[i-1] == p[j-2] || p[j-2] == '.') {
                            dp[i][j] = dp[i][j-2] || dp[i-1][j];
                        } else {
                            dp[i][j] = dp[i][j-2];
                        }
                    }
                } else {
                    dp[i][j] = ((s[i-1] == p[j-1] || p[j-1] == '.') && dp[i-1][j-1]);
                }
            }
        }
        return dp[slen][plen];
    }
};