MLE Error for Regex Matching DP

#1

Not able to understand what’s giving the MLE Error and wrong answer in some cases.My code:

#2

hello @Vishal_234

this question is bit different than wildcard matchinh problem so same code will not work here.
regarding mle-> it is giving mle because in worst case dp will 10000 X 10000 size which will consume to much memory.
so try bottom up approach and use 2 X N size dp array to store current and previous state.

for ur reference->

We define dp[i][j] to be true if s[0…i) matches p[0…j) and false otherwise. The state equations will be:

dp[i][j] = dp[i - 1][j - 1], if p[j - 1] != ’ ’ && (s[i - 1] == p[j - 1] || p[j - 1] == ‘.’); dp[i][j] = dp[i][j - 2], if p[j - 1] == ’ ’ and the pattern repeats for 0 time; dp[i][j] = dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == ‘.’), if p[j - 1] == ‘*’ and the pattern repeats for at least 1 time. And you may further reduce the memory usage down to two vectors (O(n)).

  bool isMatch(string s, string p) {
    int m = s.size(), n = p.size();
    vector<bool> pre(n + 1, false), cur(n + 1, false);
    cur[0] = true;
    for (int i = 0; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p[j - 1] == '*') {
                cur[j] = cur[j - 2] || (i && pre[j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
            } else {
                cur[j] = i && pre[j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
            }
        }
        fill(pre.begin(), pre.end(), false);
        swap(pre, cur);
    }
    return pre[n];
}
#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.