Doubt in this recursion problem

#1

Solution Link-https://ide.codingblocks.com/s/375310
Question Link-https://leetcode.com/problems/regular-expression-matching/submissions/

#2

hello @mridulmohanbagri17
what doubt u have in this problem ?

#3

The code is passing some test cases but not the others I can’t find the error where it is failing.

#4

yeah it will not pass all cases becuase this recursive solution has high time complexity.

u need to optimise it by applying dynamic programming.

also make sure u r not giving 0 length to susbstr function. that will throw an error.

#5

class Solution {
public:
bool isMatch(string s, string p)
{
//Base Case
if(p.length()==0)
return s.length()==0;

    bool firstchar=(s.length()>0) and ((p[0]==s[0])or p[0]=='.');
    
    if(p.length()>=2 and p[1]=='*'){
        return isMatch(s,p.substr(2,p.length())) or (firstchar and isMatch(s.substr(1,s.length()),p));
    }
        
    else{
        return firstchar and isMatch(s.substr(1,s.length()),p.substr(1,p.length()));
    }
    
}

};

Now it’s working.

#6

yeah i checked it is getting accepted, but it is not optmised one.
and will surely give tle if u try to submit it on any other online judge.

do try to solve it using dp.

#7

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.