regexp.cc

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int s_size = strlen(s);
        int p_size = strlen(p);
        vector<vector<int>> dict(s_size + 1, vector<int>(p_size + 1, -1));
        is_match(s, p, 0, 0, dict);
        return dict[0][0] ? true : false;
    }
    
    int is_match(const char *s, const char *p, int si, int pi, vector<vector<int>> &dict) {
        if (si < dict.size() - 1 && pi < dict[0].size() - 1) {
            if (dict[si][pi] != -1) {
                return dict[si][pi];
            } 
            if (*(p+pi+1) == '*') {
                if (*(s+si) == *(p+pi) || *(p+pi) == '.') {
                    dict[si][pi] = is_match(s, p, si+1, pi, dict) || is_match(s, p, si+1, pi+2, dict) || is_match(s, p, si, pi+2, dict);
                    return dict[si][pi];
                } else {
                    dict[si][pi] = is_match(s, p, si, pi+2, dict);
                    return dict[si][pi];
                }
            } else {
                if (*(s+si) == *(p+pi) || *(p+pi) == '.') {
                    dict[si][pi] = is_match(s, p, si+1, pi+1, dict);
                    return dict[si][pi];
                } else {
                    dict[si][pi] = 0;
                    return 0;
                }
            }
        } else if (pi < dict[0].size() - 1) {
            if (*(p+pi+1) == '*') {
                dict[si][pi] = is_match(s, p, si, pi+2, dict);
                return dict[si][pi];
            } else {
                dict[si][pi] = 0;
                return 0;
            }
        } else if (si < dict.size() - 1){
            dict[si][pi] = 0;
            return 0;
        } else {
            dict[si][pi] = 1;
            return 1;
        }
    }
};