Sir I am quite confused with Regex condition

#1

What does match zero or more of previous occurrence mean?
Like for following input, I am giving output as 1
abbbcd
ab*cd
(ie, matching ‘b’ before * with 3 ‘b’ in the original string).

My code passes 3 cases and rest do not pass.

#2

That is if the previous character is c:

If c != ‘.’ then match as many instances of c.
For example, “ab*cd” = {acd, abcd, abbcd, … }

If c == ‘.’ then the characcters can be anything
for example, “a.*cd” = {acd, aacd, aaaaacd, absfud, … }

1 Like
#3

I have updated the code, but getting MLE & WA for few cases.

#4

Please share the code.

#5

CodeLink: https://ide.codingblocks.com/s/327918

#6

There are some issues. Take a look at this code, and try to implement on your own, else’ I’ll help

bool isMatch(string s, string p) {
    if (p.empty()) { return s.empty(); }

    if ('*' == p[1])
        // x* matches empty string or at least one character: x* -> xx*
        // *s is to ensure s is non-empty
    {
        return (isMatch(s, p.substr(2)) || !s.empty() && (s[0] == p[0] || '.' == p[0])
                && isMatch(s.substr(1), p));
    }
    else {
        return !s.empty() && (s[0] == p[0] || '.' == p[0]) && isMatch(s.substr(1), p.substr(1));
    }
}

This is a bruteforce, for your help, you just take hints and write the optimized dp solution yourself.
It will be very helpful to you if you are able to write the code on your own.

If you have any doubts, feel free to reach back.

1 Like
#7

Implemented successfully.

1 Like