Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Leetcode 10: Regular Expression Matching (recursive + memo)
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment