Wildcard matching :two test cases not passing

#1


can u please tell me what is wrong in my code.
Also,the constraints Size(str)*Size(pattern) < 100000000 is given and i can’t figure out the size of dp array in both bottom up and top down.

#2

@sjduttabbsr2017 For one test case it is giving TLE because you need to optimize your solution for pat[m-1]==’*’, here you are calling recursively for k times.
Better solution here is to check
if(pat[m-1]== ’ * ')
then we have 2 options
op1 = regexMatch(str, pat, k-1, m) -> it means to skip the current char in text
op2 = regexMatch(str, pat, k, m-1) -> it means skip the current char in pattern because it can be empty also.

#3

@sjduttabbsr2017
One more base case you have to check is suppose n==0 which means that all the characters of text are covered.
Now we are remaining left with the chars of pattern only so it is possible that all the remaining characters are "".
for eg:- pattern = “” , text ="*" here pattern empty but text is only '’.

You can also have a look at the code for better understanding, i have done the required changes in your code https://ide.codingblocks.com/s/231712

#4

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.