Wildcard pattern matching

#1

It is giving TLE for 1 test case, please tell the error.
With dp code:

without dp:

#2

Hello @poorva2145,

Your code is giving wrong output for the case:

  1. aas
    a*a*?*

  2. abcdefgh
    ***fgh***

Correct your code for these test cases.

1 Like
#3


Sir I corrected the code for above test cases but then also it is giving TLE for one test case.

#4

Hey @S18ML0016,

I have corrected your code:

Give a like if you are satisfied.

1 Like
#5


Sir, in 2nd and 3rd base condition, why it is (j>y) and (i>x) ?
I think it should be (j>=y) and (i>=x) ?

#6

Hello @poorva2145,

This is because the memorization matrix has values at y and x column and row resp.
There is slight modification i have made in this code that will clear your confusion:

So,

  1. condition (j>y) refers to the case when the pattern has been traversed completely.
    But, the original string still has some characters left.

  2. condition (i>x) refers to the case when the original string has been traversed completely.
    But, the pattern still have some untraversed characters.

Hope, this would help.

1 Like