Leetcode 10: Regular Expression Matching (recursive + memo)

leetcode_10b.cpp

#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool isMatch(string s, string p, int is, int ip, vector<vector<int>>& dp) {
    if (dp[is][ip] != 0) return (dp[is][ip]==2);
    int ois = is, oip = ip; //original is and ip values

    while (is < s.size() && ip < p.size()) {
        if (ip+1 < p.size() && p[ip+1] == '*') {
            while (is < s.size()) {
                if (p[ip] != '.' && s[is] != p[ip]) {dp[ois][oip]= (isMatch(s, p, is, ip+2, dp) ? 2 : 1); return dp[ois][oip]==2;}
                if (isMatch(s, p, is, ip+2, dp)) {dp[ois][oip]=2; return true;}
                is++;
            }
            ip += 2;
        }
        else if (p[ip] == '.') { is++; ip++; }
        else { //match normal (non-wildcard) character
            if (s[is] != p[ip]) {dp[ois][oip]=1; return false;}
            else { is++; ip++; }
        }
    }
    //trailing wildcards
    if (is==s.size() && ip+1 < p.size() && p[ip+1]=='*') {
        dp[ois][oip] = (isMatch(s, p, is, ip+2, dp) ? 2 : 1);
        return (dp[ois][oip] == 2);
    }

    bool matched = (is == s.size() && ip == p.size());
    dp[ois][oip] = (matched ? 2 : 1);
    return matched;
}

bool isMatch(string s, string p) {
    vector<vector<int>> dp (s.size()+1, vector<int>(p.size()+1, 0));  //key[is,ip] values: 0=unvisited, 1=visited false return, 2=visited true return 
    return isMatch(s, p, 0, 0, dp);
}

int main() {
    string s = "abcaaaaaaabaabcabac"; //"a"; //"ab"; //"aa"; //"mississippi";//"aab";
    string p = ".*ab.a.*a*a*.*b*b*"; //".*..a*"; //".*"; //"a*"; //"mis*is*p*.";//"c*a*b";
    cout << isMatch(s, p) << "\n";
    return 0;
}