DP 34. Wildcard Matching | Recursive to 1D Array Optimisation 🔥

[@gaurishaaaa]

DP on strings understood ✅ From hating and fearing DP to love doing it.. all the way grateful to you.

[@mohitagarwal3639]

Hey Striver you have helped me a lot in logic building . I paused the video right at 4:42 after understanding what question is all about and was able to code the solution all by myself. It feels really great when I solves a question (all by myself) which was next to impossible for me a month back. I always thank you the moment green signal of "Correct Answer" pops up and you deserve it. Understood🙂🙂

[@shatadal_das]

Hey, can we connect ? I'm looking for a DSA partner..

[@umerqureshi8184]

@@shatadal_das yes, lets go

[@kancherladevisrivenkat21bc91]

You spoke my heart bro 😁

[@ajringtones9574]

Thanks for commenting, brother! I had literally started watching the solution without trying it myself. Although I understood the problem very well, when I was at 4:20 in the video, I saw your comment, and it hit me hard (understanding the problem yet watching the solution without trying). That realization made me stop the video right at 4:42, and I went on to solve it myself. Thank you, brother!

[@realProLog]

After looking at the comments of people who paused at 4:42, I got motivated and went straight to solving the problem. And I solved it without any help from an external source. Time taken: 40 mins (I know it's too much... But solving LC Hard by myself means a lot to me. 😭😭 Love you, striver, 😘😘

[@aps8874]

Wow, I solved this on my own, and I loved it. I used to fear recursion a lot, but your videos helped me a lot, and now I can solve this hard-level question on my own, which jumps my confidence to another level. Thanks, Striver. I will be forever grateful for your lectures.

[@sayandey2492]

I remember about 2 months back, I had seen this problem and closed it after reading the problem statement for 2 minutes, understanding it can't be solved by me in any way. Today I am able to solve it within 30 minutes without seeing the video at all 🤯. Thanks Striver. You have love of all aspiring coders 🙌 🙌

[@TheLearningLab898]

me too bro,

[@ugthesep5706]

me too

[@happysatan5554]

where are you working?

[@adebisisheriff159]

I do not know how to thank you Striver..... Thank you for being an amazing person and coder. Thank you for being a shoulder to lean on..... 🥰🥰🥰🥰🥰🥰🥰

[@ali-wz6nz]

00:00 - Wildcard matching problem 06:08 - Recursion is a helpful approach for solving string matching problems. 12:07 - The star symbol in the text represents a wildcard that can match any number of characters. 17:55 - Comparisons have been done as required 23:15 - The time complexity will be exponential and the space complexity will be n x m. 28:45 - Convert the given code into dynamic programming using tabulation 00:08 - Convert the given code into a one-based indexing using tabulation. 38:40 - Space optimization is key when solving problems with dynamic programming.

[@utkarshpandey4881]

Really I am thankful to your for your DP series. I did all steps take help in base case. but feel good to code and solve.

[@ahanavishwakarma3956]

I was able to think of almost the whole approach without watching your explanation. Couldn't be more grateful!

[@toshangupta7306]

More optimized version for computing 0th index of curr --> It is checking if the string p contains only * If previously we found 0th index to be false that means it contains char other than * --> Assign false Otherwise if previously it was true --> If curr index of string is * --> true else ->> false bool isMatch(string s, string p) { int m=s.length(); int n=p.length(); vectorprev(m+1,false),curr(m+1); prev[0]=true; for(int i=1;i

[@raghuvamsi4879]

Tysm striver, the way you explained these dp problems so far is really really awesome, In fact I was able to come up the last 3 problems in "DP on Strings" set by myself! This is all because, your explanation for previous questions is damn good which made me understand the true essence of dp! Keep the 🔥going and all the very best striver ❤!

[@stith_pragya]

UNDERSTOOD.....Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@vishious14]

Striver, you’re the greatest teacher I’ve ever had. I was able to build the logic for this question and the previous question all by myself and solved in all three approaches. Thanks a lot man. This is GOLD !!!!

[@yashshetty7326]

I could have never thought that I could solve a Leetcode hard question by myself. This dp playlist is the best playlist in KZbin and I thank you Striver for such an amazing playlist.

[@deviprasad_bal]

same dude, i just can't believe how easy striver made string matching dp for me, I did this myself and I can't believe it.

[@romanshrestha7510]

same dude i can't believe this

[@prajwalshetti3655]

The part where the pattern string gets exhausted can also be this way in tabulation for(int i=1;i

[@ankitpandey7262]

Anyone following the playlist from the start can able to do these Leetcode Hard Ques easily without watching the video. Thanks for this amazing content.

[@melvinfrancis7525]

In tabulation to check the base case instead of iterating from the beginning every time you can simply check if the previous state is true and the current value = '*". for(int i = 1 ; i

[@parthsalat]

Dev Manus

[@cheriviralakarthik]

✌

[@ankitmeena5637]

can you explain it more clearly ?? please

[@kaushik.aryan04]

you are a real one

[@anonymous10906]

Previous state 1 signifies that upto that index all characters are '*' and if the current index in wild string is also '*' then the wild string upto the current index has all its characters as '*'@@ankitmeena5637

[@stolenkid2121]

I messed up this question with regular expression matching, I think regex matching is a bit tougher than this, thank you for this explanation, I hope the next lecture will be regex matching one . I solved that regular expression matching but would like to hear again from you😊

[@takeUforward]

Its the same question !

[@amitkoushik5504]

@@takeUforward it's similar not same

[@saibingi6980]

@@amitkoushik5504 yes

[@arunm619]

@stolenkid2121 how is it different from Wildcard matching

[@brokegod5871]

How did you solve it?

[@prerna_mishra]

This series has brought me to the point where I can build intuition and code by myself within minutes ( which was unimaginable approx 15 days back). All thanks to you nd your constant efforts!! Extremely Grateful _/\_

[@AbhayAkuti]

How much time did you take to complete this playlist?

[@prerna_mishra]

15 days@@AbhayAkuti

[@Rahul_Mongia]

@@AbhayAkuti 8 months

[@ibtesamansari]

Bro , I literally enjoyed this lecture, I am filled with joy , Awesome explanation

[@mantrarajgotecha3055]

You just not make us understood dp on strings but you make us feel how to think and feel about dp on strings. Hats off you !!

[@codermal]

We can further optimize by keeping a flag and checking for current characters only in base case (Ex: pattern = ****ab, text=ab) i.e: int m=pattern.size(),n=text.size(); vector prev(n+1,false),temp(n+1,false); prev[0]=true; bool flag=true; for(int i=1;i

[@abhishekNITT]

Base Case for Tabulation dp[0][0]=true; if(pattern[0]=='*') { int i=1; while(i

[@naman_goyal]

Amazing content. Now I start solving before watching video and then watch it completely to learn how to explain better and writing clear code. Thankyou ❤️

[@Parthj426]

#Understood | Wonderful series of DP on strings | Definitely feeling confident !

[@parthsalat]

*Notes* 1. Those who already know the question can start the video from 4:40 2. Using .at() operator for string and vectors does automatic bound checking. It's much safer than using [ ] 😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏 *Important timestamps* Recursion - code: 29:47 - complexity: 26:00 Memoization - code: 31:00 - complexity: 26:55 Tabulation code: 38:21 Space optimisation code: 42:26 😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏😏 *Striver's this code snippet (**38:07**) runs in O(N^2) time. I've optimised it to run in O(N) time* // ---------------------------------- Code snippet begins ---------------------------------------- //if there is no text, the pattern must be all * for answer to be true for(int patternIndex=1; patternIndex

[@Nutrino259]

😏😏😏😏😏😉😏😏😏😏😏

[@shubhamsalunkhe137]

Understood It was great learning DP on strings from your striver🙌🙌 Thank you for everything you have done🙌

[@ajitpalsingh606]

Here Striver is assuming S1 to b ehaving character * and ? and S2 string that is to be matched. But In Leetcode ,there is opposite S1 string is to be matched and S2 string contains * and ? therefore ,Base condition will change if(i

[@koushalsharma7041]

Understood the entire DP on Strings. Thankyou so much for the quality videos !!!!!!!!!!!!

[@ani68]

+1

[@ArnabJhaYT]

@@ani68 found the legend aniruddha :)

[@ameypate9610]

Approach to this problem is explained well, and optimizations are interesting to perform.

[@googleit2490]

Done and dusted in the DP revision :) (31 mins) Nov'17, 2023 10:11 pm

[@deependrasinghshekhawat8107]

Solved this questions along with Regular Exapression matching, all on my own, All thanks to you Striver!!!

[@devanshkumar3816]

The way you taught the space optimization in previous videos it got onto my tip and was able to space optimize the code on my own... Much respect !!! orz I did space optimisation this way: int n = s.length(), m = t.length(); vector dp(m + 1, false); dp[0] = true; for(int j = 1; j

[@hitengarg3167]

Keep up the good work Bro!!🔥🔥🔥. Always scared of this question, whenever I see it, I immediately skip it...But you made it so so so simple to understand, that without even looking at the solution I was able to come up with code. The entire DP series is AWESOME🔥🔥🔥

[@mohaimenchowdhury]

Hey Striver!! I am a great fan of your videos. Can you make series for the other string matching algorithms like KMP/Rabin Karp also? I know you are the best person right now to teach those at very intuitive level.

[@johar3737]

Understood. Now I am able to make logic and intuition behind the question. Thanks Striver

[@gauravbhardwaj6656]

for more optimization we can merge multiple continuous '*' with single '*' before applying DP and we can reduce those last 1d array to single integer value.

[@codingachinilgtifirbhikrrh9009]

bhai ky kare ga itta optimize krke vese h boht ho chuka

[@sushant8686]

@@codingachinilgtifirbhikrrh9009 😀😀😀😀😀😀

[@vanshsehgal9475]

@@codingachinilgtifirbhikrrh9009 vahi bhai..😂😂

[@ritishbhardwaj9190]

good one

[@amitkoushik5504]

Bas kr pagle rulayega kya😂😂🥲

[@sauravchandra10]

Understood the entire DP on strings, thanks a lot!

[@SYCOA12CHAITANYAASOLE]

Sir Hatts Off to you, Keep Going...

[@preetisahani5054]

Awesome explanation, I missed the all stars base case while solving on my own,

[@electricindro2236]

Amazing explanation! Understood!

[@CODEWITHEASE-u8l]

STRIVER YOU ARE G.O.A.T

[@ted_mosby]

almost got 70% done on my own for a hard problem thanks

[@janardhan2jordan]

we can also use this two line code for setting curr[0] and it saves some time as well just we also have to initialize flag as true outside the first for (i) loop and this will be placed in inside first for loop just like striver's.. Thankyou striver for all the efforts if(flag == true && pattern[i-1] != '*')flag = false; curr[0]=flag;

[@suyashjain3223]

Completed DP on strings successfully!!

[@mdmudassiralam5490]

We can make the base case simpler if(ind1

[@keshavprasad1017]

You made DP feel like a cup of coffee ☕️ ...

[@ritikshandilya7075]

Thankyou so much for great explanation Striver

[@ntgrn-pr5yx]

thankS striver ,LOVE YOUR WORK

[@amanbhadani8840]

I loved the way you handled all the valid number of charcters possible starting from zero for astrik.I thought of looping it but your explanation was so much simple and easy to understand.

[@chanchalroy3417]

Just wow 😮 understood 👏❤️

[@suhaanbhandary4009]

Understood!!, and solved this question before explanation, Thanks for such series !!

[@jasmeenkaur6001]

thank you so much striver...................... First time in my life i understood tabulation and able to write code by myself. thankyou so soooooooooooo muchhhhhhhhhhhhhhhhhhhhhh.

[@hashcodez757]

"UNDERSTOOD BHAIYA!!"

[@arnabsarkar5245]

Understood sir 🔥🔥

[@champion5946]

US for base case In C++ we can also do for(int i = 1; i

[@AyushGupta-re5yp]

This is legit insane! Gold Content. 1st Hard Problem on my own. All credits to you!

[@kunalgupta343]

I think we don't need nested loop for *, for(let j=1; j

[@sauravlogsvio1891]

This is awesome. But the base case -> where pat[i] remains.. while string is exhausted, probably needs some more treatment. For example - "c*a*b" matches with "aab" because - c* means 0 c's or any number of characters. For instance, ab*c matches "ac", "abc", "abbc", "abbbc", and so on.. Need to check if all the chars are '*' or its (char) followed by '*' like [w*x*y*....] kind of pattern which means there can be no characters at all.

[@chetanraghavv]

I think you are confusing this question with Regular Expression Matching Here, "c*a*b" does not match "aab" because, if first * is a and second is NULL then string becomes "caab" which does not match "aab"

[@ChandraSekhar-mz8xy]

I would also like to add : > curr[0] depend on prev[0] and if the current char is '*' o r not. > instead of 'isAllStars' method (given in article) you can use this single line : curr[0] = p.charAt(i-1) == '*' && prev[0];

[@sarveshsugandhbarnwal9809]

So blessed to have teacher like You, Very clean explanation. Thank You Striver

[@harshraj3522]

thank you striver ❤

[@ajitpalsingh606]

Done Recursion on my own

[@ztrixx3280]

when i was trying to solve this question, i thought of looping through until i find next character to star(*), recursion doesn't even came across my mind at 5:51 (video timestamp) after getting WAs i realised that it was meant to be solve the way Raj explained.

[@mayankbhugra6193]

Amazing !!! explanation and energy. Thanks for the content ❤

[@RohitKumar-dy2gc]

just saw the recursion and rest is super super simple

[@kazuma0803]

First hard question done on my own. Thank you Striver

[@amitkoushik5504]

I also solved it till space optimization on my own ....and started dancing😂❤❤🎉all credits to striver🎉❤

[@GodOfFaith]

you worte the code on your own , doing question on your own means , you found the logic on your own , which you didn't but still its good that you solved the problem

[@Hrushi_2000]

Understood. Thankyou Sir.

[@aniruddhakotal1534]

Till how much optimized is needed in interviews? will they expect space optimized, or , till tabulation is mandatory?

[@lohesh9822]

For the base case, couldnt you just write , for(int i=1;i

[@OMPRAKASH-is7fj]

greatful to u

[@arpankoley4256]

For the leetcode version pattern p is declared second , so in 1D array optimization i have taken prev array as dp[m+1] = {false}; Here is a simplified base case for this--> dp[0] = true; for(int j=1;j

[@felixkimbu8484]

Was very helpful. My problem did not require '?' so I just removed it from the condition. Also, loops where not allowed so I created another recursive function to use it in place of the for loop.

[@dsp-io9cj]

dp[0][0]=1; for(int i=1;i

[@sahilgagan2242]

61% done bro thankyou so much ....

[@tasneemayham974]

BESTT TEACHERR EVERR!!!

[@urstrulyjatin]

Thanks mate 🙏

[@akshayjain8810]

can we run a loop when pattern[ i ] == ' * ' and return accordingly

[@asishcodes]

20:30 there is a small typo. It will be false

[@DevashishJose]

Understood thank you so so much.

[@GodOfFaith]

if(p.charAt(j)=='*'){ help(i-1,j-1,s,p); // i am curious about this condition where , i can match the '*' with one character and then move both i and j pointers . } for example s= abe ; p=ab* ; in next iteration i will go s=ab and p=ab ; // isn't this possible??

[@arpnasjs9825]

Did space optimization on my own in a different way...Thank u for this series.

[@ganeshkamath89]

Thanks Striver. Understood. Why have you done bitwise or (|) instead of logical or (||) for asterisk case?

[@anuragpandey8165]

It is because the only possible return values of function are 0 and 1. Hence the bitwise OR can return the correct answer as 0 | 0 = 0, 0 | 1 = 1, 1 | 0 = 1, 1 | 1 = 1. Also the bitwise operations are faster and striver is a CP guy.

[@ganeshkamath89]

@@anuragpandey8165 , why have you written 0 | 0 = 1? Also are you sure that bitwise or is faster? because even logical or does the same 0||0 = 0 0||1 = 1 1||0 = 1 1||1 = 1 Where as bitwise or does the operation bitwise (agreed that we are dealing with 1 bit here, but still I am not convinced).

[@srikrishnabejawada3126]

amazing ❤

[@santoshb7776]

understood sir 🙏🙏

[@AsifHussain-gl4ci]

what will happen if * or ? are in s2 i am not understanding how that case is considered

[@abhinavgupta4778]

Just an observation: Space optimization into two array will be very easy if you make the dp matrix as dp[text.size][pattern.size] rather than dp[pattern][text].

[@Your_Boy_Suraj]

Wrong Answer 276 / 354 testcases passed Input s = "aab" p = "c*a*b" Use Testcase Output false Expected true

[@KaifKhan-sb2yr]

same with me did you got the solution ?

[@arihantjammar8888]

Understood 😊

[@mayankverma1169]

Is it really okay to just copy the recurrence for tabulation, because then I would not know how tabulation is working and that way I will never be able to tabulate directly , atleast that's what i feel

[@VinayKumar-xs6el]

agreed same happening with me

[@gunduboinadileep9523]

understood!!. thank you

[@abhirupray2494]

Understood completely

[@Sara-ed3jq]

I was able to solve the question and pass 80% of test cases by myself, which was possible only because of you. Understood

[@chaitanyatanwar8151]

Thank you!

[@joshrak3412]

base case in tabulation for this condition (i>=0 && j

[@shivamprajapati407]

a doubt...can we not first find the lcs and then decrement the jth pointer by length of str2-lcs in that way we could overcome the recursion for finding the length ' * ' could take....?

[@aayushranjan3675]

For handling the '*' case, can we do it by using a for loop for calculating the length to be matched and then call the recursive function? The runtime becomes very slow on doing this. Can you tell me why this happens as the number of recursive calls would be approx the same for both the cases. Thanks.

[@adarshmishra7113]

bhaiya loved your explanation i studied almost the whole DS and ALGO by your channel only , thankyou so much for all the content you had put and presently you are putting

[@kaushalshinde8]

WOW! wrote code myself Thank You Striver!!

[@anhadwadhwa2844]

We can optimise this further using a single 1-d array as well, by taking a variable storing prev value at j-1 index. Moreover, the third base case can be optimised to curr[0]=prev[0]&&(p[i-1]=='*'); and the code for 1-1d array is: vector prev(m+1, 0); prev[0]=1; for(int i=1; i

[@goooo9561]

nice approach