Base Case for Tabulation dp[0][0]=true; if(pattern[0]=='*') { int i=1; while(i
@pranavm002
Жыл бұрын
On Leetcode : only 1731/1811 passes in the bottom up (tabulation) apparoch "*a?b*" ""zacabz" This testcase fails for some reason
@rahultiwari7714
2 жыл бұрын
hats down sir!!! this is happen when god himself came on earth to teaches us this beautiful concept... and thank u soo much for whatever u r doing for us... and mark my word agar coding and logic building me revolution aayi toh voh appke vajah se hi aayegi... thank u soooo os ssoooo much
@nikhilkotiya8062
2 жыл бұрын
I can code solution without see your solutions, thank you a lot bhaiya for making such kind of video ❤️❤️❤️❤️. Its help me a lot for improving my skill and you know what my favorite topic dp and if some one ask me why then I reply them by saying because I learn from striver bhaiya🤩.
@himanshuagrawal8012
2 жыл бұрын
We can remove that for loop in base condition in tabulation, by this code , we can na ? @STRIVER @TAKE_U_FORWARD for(int j=1; j
@studynewthings1727
5 ай бұрын
Understood
@verma_jay
11 ай бұрын
understood
@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
23 күн бұрын
me too
@mohitagarwal3639
2 жыл бұрын
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
2 жыл бұрын
Hey, can we connect ? I'm looking for a DSA partner..
@umerqureshi8184
Жыл бұрын
@@shatadal_das yes, lets go
@kancherladevisrivenkat21bc91
2 ай бұрын
You spoke my heart bro 😁
@stolenkid2121
2 жыл бұрын
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
2 жыл бұрын
Its the same question !
@amitkoushik5504
Жыл бұрын
@@takeUforward it's similar not same
@saibingi6980
Жыл бұрын
@@amitkoushik5504 yes
@arunm619
4 ай бұрын
@stolenkid2121 how is it different from Wildcard matching
@brokegod5871
2 ай бұрын
How did you solve it?
@tn4122
2 жыл бұрын
Is the code working for everyone in leetcode? If yes please share the code. I'm not getting all the test cases passed.
@maxtennyson01
Жыл бұрын
just sawp the strings at the beginning and try again
@prerna_mishra
2 жыл бұрын
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
@yashshetty7326
Жыл бұрын
I could have never thought that I could solve a Leetcode hard question by myself. This dp playlist is the best playlist in KZitem 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
@B-Aparnasai
2 жыл бұрын
me at 20:50 stopped and thinking how it is true😅
@Your_Boy_Suraj
Жыл бұрын
Wrong Answer 276 / 354 testcases passed Input s = "aab" p = "c*a*b" Use Testcase Output false Expected true
@KaifKhan-sb2yr
9 ай бұрын
same with me did you got the solution ?
@pratyakshsinha6292
Жыл бұрын
fails for test case pattern = "*" text = "aa"
@lohesh9822
3 ай бұрын
For the base case, couldnt you just write , for(int i=1;i
@gauravbhardwaj6656
2 жыл бұрын
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
2 жыл бұрын
bhai ky kare ga itta optimize krke vese h boht ho chuka
@sushant8686
2 жыл бұрын
@@codingachinilgtifirbhikrrh9009 😀😀😀😀😀😀
@vanshsehgal9475
2 жыл бұрын
@@codingachinilgtifirbhikrrh9009 vahi bhai..😂😂
@ritishbhardwaj9190
Жыл бұрын
good one
@amitkoushik5504
Жыл бұрын
Bas kr pagle rulayega kya😂😂🥲
@melvinfrancis7525
2 жыл бұрын
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
2 жыл бұрын
Dev Manus
@cheriviralakarthik
2 жыл бұрын
✌
@ankitmeena5637
Жыл бұрын
can you explain it more clearly ?? please
@kaushik.aryan04
Жыл бұрын
you are a real one
@anonymous10906
10 ай бұрын
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
@toshangupta7306
3 ай бұрын
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
@SS-pf8zm
Жыл бұрын
Why does this code not run on leetcode? #include int f(int i, int j, string pattern, string text, vector & dp){ // i is the ptr at pattern and j is the pattern at text if(i < 0 && j < 0) return true; if(i < 0 && j >= 0) return false; if(j=0){ for(int ii=0; ii
@deepankerchaudhary7187
2 жыл бұрын
"aab" "c*a*b" leetcode giving true for this but your code giving false
@kazuma0803
2 жыл бұрын
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
@AsifHussain-gl4ci
4 ай бұрын
what will happen if * or ? are in s2 i am not understanding how that case is considered
@naman_goyal
2 жыл бұрын
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 ❤️
@mdmudassiralam5490
2 жыл бұрын
We can make the base case simpler if(ind1
@adebisisheriff159
9 ай бұрын
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..... 🥰🥰🥰🥰🥰🥰🥰
@ahanavishwakarma3956
2 жыл бұрын
I was able to think of almost the whole approach without watching your explanation. Couldn't be more grateful!
@fettuccine794
8 ай бұрын
wrong solution, not accepting on leetcode
@jeet7000
Жыл бұрын
thanks sir..solved it myself
@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
14 күн бұрын
agreed same happening with me
@ankitpandey7262
2 жыл бұрын
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.
@gaurishaaaa
3 ай бұрын
DP on strings understood ✅ From hating and fearing DP to love doing it.. all the way grateful to you.
@ajitpalsingh606
Ай бұрын
Done Recursion on my own
@sahilgagan2242
2 жыл бұрын
61% done bro thankyou so much ....
@adarshkumargupta.
Жыл бұрын
Can you make a video on Regular Expression Matching Problem on leetcode ???
@pranavsharma7479
2 жыл бұрын
this ques and regex ques are completely different, dont confuse b/w them
@akshayjain8810
2 жыл бұрын
can we run a loop when pattern[ i ] == ' * ' and return accordingly
@devanshkumar3816
2 жыл бұрын
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
@LBK3
Жыл бұрын
understood ❤
@ganeshkamath89
2 жыл бұрын
Thanks Striver. Understood. Why have you done bitwise or (|) instead of logical or (||) for asterisk case?
@anuragpandey8165
2 жыл бұрын
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
2 жыл бұрын
@@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).
@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
@kunalgupta343
Ай бұрын
I think we don't need nested loop for *, for(let j=1; j
@mantrarajgotecha3055
2 жыл бұрын
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 !!
@NARUTOUZUMAKI-bk4nx
9 ай бұрын
UNDERSTOOD! This is my code for space optimization bool isMatch(string str2, string str1) { int n = str1.size(); int m = str2.size(); vector prev(m+1),curr(m+1),e(n+1); prev[0]=1; for(int k=1;k
@piyushjaiswal9192
Жыл бұрын
int rec1(string pattern,string str,int i,int j, vector&dp) { if((i
@jasmeenkaur6001
2 жыл бұрын
thank you so much striver...................... First time in my life i understood tabulation and able to write code by myself. thankyou so soooooooooooo muchhhhhhhhhhhhhhhhhhhhhh.
@googleit2490
Жыл бұрын
Understood :) Almost done by myself except (f(i-1,j)) condition July'31,2023, 10:56 pm
@arijitdas4560
2 жыл бұрын
in 24:34 there is nother case that if in s1[ind]=='?' then also I can return true....but here the else case is hadling that part...done wisely
@UECAshutoshKumar
3 ай бұрын
Understood !
@codermal
2 жыл бұрын
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
@fanofabdevillersandmathslo5960
Ай бұрын
Understood
@jeet7000
Жыл бұрын
my recursive solution class Solution { public: bool solve(int i,int j,string& s,string& p,vector& dp){ if(i
@bhuoneparmar5098
Жыл бұрын
understood i done leetcode hard without even watching video and also write tabulation; :) Thanks a lot bhaiya!! (~ ̄▽ ̄)~
@ztrixx3280
2 жыл бұрын
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.
@koushalsharma7041
2 жыл бұрын
Understood the entire DP on Strings. Thankyou so much for the quality videos !!!!!!!!!!!!
@ani68
2 жыл бұрын
+1
@ArnabJhaYT
2 жыл бұрын
@@ani68 found the legend aniruddha :)
@divyansh2212
2 жыл бұрын
As always "understood"
@ujjalsaha428
2 жыл бұрын
As always "understood"
@johar3737
2 жыл бұрын
Understood. Now I am able to make logic and intuition behind the question. Thanks Striver
@kartikrameshchavan6662
Жыл бұрын
Understood 🙏
@IrfanAhmed-vf7nb
4 ай бұрын
I was right till memoization😅 but can't do the tabulation can't compute base conditions😢
@VikashYadav-px8ei
Жыл бұрын
Understood 🎉
@vandanapranaviam
2 жыл бұрын
Very good explanation Striver😇
@googleit2490
10 ай бұрын
Done and dusted in the DP revision :) (31 mins) Nov'17, 2023 10:11 pm
@suhaanbhandary4009
Жыл бұрын
Understood!!, and solved this question before explanation, Thanks for such series !!
@shubhii1602
3 күн бұрын
what about the case where s1="ab?" and s2="ab"
@raghavmanish24
Ай бұрын
understood ....this time i skip the optimisation of tabulation method
@itslol6504
Жыл бұрын
Understood ! This Guy is making videos at 4 am !! Crazy
@AyushGupta-re5yp
Жыл бұрын
This is legit insane! Gold Content. 1st Hard Problem on my own. All credits to you!
@OMPRAKASH-is7fj
11 ай бұрын
greatful to u
@ted_mosby
13 күн бұрын
almost got 70% done on my own for a hard problem thanks
@dddoes9528
Жыл бұрын
can anyone explain as i am getting wrong ans in leetcode question s="aa" and q="*",thanks in advance
@sameekshamurdia5-yeariddph649
Жыл бұрын
understood
@stith_pragya
8 ай бұрын
UNDERSTOOD.....Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
@arpitkumarmishra2734
Жыл бұрын
solved by for looping method by myself.......❤❤❤❤
@wisdomkhan
Жыл бұрын
You are one of the most successful and disciplined persons I have known in my life.
@SYCOA12CHAITANYAASOLE
Ай бұрын
Sir Hatts Off to you, Keep Going...
@user-zn3be9ik1x
Жыл бұрын
how you guys are doing it on your own i am seriously struggling to solve these questions 🥲🥲🥲
@sauravchandra10
Жыл бұрын
Understood the entire DP on strings, thanks a lot!
@sahilkhan_cs50
Жыл бұрын
self note-It cannot be optimised to single 1d array.
@inforook2258
Жыл бұрын
Inspite of this code to check for the base case s2 is empty and s1 contains '**...' or not . for(int i=1;i
@prabhakaran5542
5 ай бұрын
Understood ❤
@shisui3645
Жыл бұрын
Gives an error for pattern="*" and text="aa"
@NidhiGupta-th2de
Ай бұрын
We can not simply return true if s[i]==*
@nishantraj7209
18 күн бұрын
if constraint start from 0 then how to handle those cases
@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 ❤!
@alconime
Жыл бұрын
Help me pleaase :- This is the tabulation code which is working fine (passed all the test cases on Leetcode and got accepted) int n = s.size(); int m = p.size(); vector dp(n+1,vector(m+1,0)); dp[0][0] = 1; for(int j=1 ; j
@A_Myth963
3 ай бұрын
Here is an easy space optimisation code class Solution { public: bool isMatch(string s, string p) { int n = s.size(), m = p.size(); vector prev(m + 1, 0), cur(m + 1, 0); // base prev[0] = 1; int j = 1; while (j
@ChandraSekhar-mz8xy
2 жыл бұрын
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];
@original_gangsta_
2 жыл бұрын
What if the second string is : "abcbdef"? Will this solution work for this test case also?🤔
@kedarsatwik6938
Жыл бұрын
no need of isAllStars function for (int i = 1; i
@batchupranav231
Жыл бұрын
can r=this be done using longest common subsequences
@sagnik_20
Жыл бұрын
for(int j=1; j
@qihse1531
Жыл бұрын
Great explanation. Bases cases most annoying to me
@yashwanthsai762
8 ай бұрын
this is different in leetcode right? it's give wrong asnwer for few test cassrs
@brokegod5871
2 ай бұрын
Did anyone try the regex matching one?
@parthsalat
2 жыл бұрын
*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
17 күн бұрын
😏😏😏😏😏😉😏😏😏😏😏
@sanamdeepsingh7914
2 жыл бұрын
Understood bhaiyaa 🔥
@KAAO-rb9lh
Ай бұрын
i wonder why he says "True"😄😄
@shubhamsalunkhe137
2 жыл бұрын
Understood It was great learning DP on strings from your striver🙌🙌 Thank you for everything you have done🙌
Пікірлер: 490