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🙂🙂
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 🙌 🙌
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
I could have never thought that I could solve a Leetcode hard question by myself. This dp playlist is the best playlist in TH-cam and I thank you Striver for such an amazing playlist.
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
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
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😊
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 _/\_
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.
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.
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 ❤!
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 !!!!
*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
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
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
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.
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
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 ❤️
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
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];
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;
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.
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🔥🔥🔥
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
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.
@@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).
thank you so much striver...................... First time in my life i understood tabulation and able to write code by myself. thankyou so soooooooooooo muchhhhhhhhhhhhhhhhhhhhhh.
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.
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"
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
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
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.
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].
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.
Thank you Striver Sir, because of all the previous videos and how good you taught us DP, I myself tried the question myself, before seeing your video and my solution worked in first go. This is a great achievement for me to solve a problem that is of Hard level in Leetcode. Thank you sir
Instead of using two 1-D Arrays we can further space optimize it using a single array. For every index we require value of it's prev row and prev col if char matches and if it does not match we require prev row same col and same row prev col. We just have to maintain a variable that can store prev row prev col value and have to update it accordingly.
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
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🤩.
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🙂🙂
Hey, can we connect ? I'm looking for a DSA partner..
@@shatadal_das yes, lets go
You spoke my heart bro 😁
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 🙌 🙌
me too bro,
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
I could have never thought that I could solve a Leetcode hard question by myself. This dp playlist is the best playlist in TH-cam and I thank you Striver for such an amazing playlist.
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.
same dude i can't believe this
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
Dev Manus
✌
can you explain it more clearly ?? please
you are a real one
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
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😊
Its the same question !
@@takeUforward it's similar not same
@@amitkoushik5504 yes
@stolenkid2121 how is it different from Wildcard matching
How did you solve it?
DP on strings understood ✅
From hating and fearing DP to love doing it.. all the way grateful to you.
I was able to think of almost the whole approach without watching your explanation. Couldn't be more grateful!
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..... 🥰🥰🥰🥰🥰🥰🥰
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 _/\_
How much time did you take to complete this playlist?
15 days@@user-tp2ds2ju4l
@@user-tp2ds2ju4l 8 months
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.
bhai ky kare ga itta optimize krke vese h boht ho chuka
@@codingachinilgtifirbhikrrh9009 😀😀😀😀😀😀
@@codingachinilgtifirbhikrrh9009 vahi bhai..😂😂
good one
Bas kr pagle rulayega kya😂😂🥲
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.
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 !!
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 ❤!
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 !!!!
*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
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
nice approach
Base Case for Tabulation
dp[0][0]=true;
if(pattern[0]=='*')
{
int i=1;
while(i
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
Understood the entire DP on Strings. Thankyou so much for the quality videos !!!!!!!!!!!!
+1
@@ani68 found the legend aniruddha :)
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.
First hard question done on my own. Thank you Striver
I also solved it till space optimization on my own ....and started dancing😂❤❤🎉all credits to striver🎉❤
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
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 ❤️
Done and dusted in the DP revision :)
(31 mins)
Nov'17, 2023 10:11 pm
Approach to this problem is explained well, and optimizations are interesting to perform.
We can make the base case simpler
if(ind1
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
Understood. Now I am able to make logic and intuition behind the question. Thanks Striver
Understood the entire DP on strings, thanks a lot!
UNDERSTOOD.....Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Sir Hatts Off to you, Keep Going...
#Understood | Wonderful series of DP on strings | Definitely feeling confident !
Bro , I literally enjoyed this lecture, I am filled with joy , Awesome explanation
"UNDERSTOOD BHAIYA!!"
Understood
It was great learning DP on strings from your striver🙌🙌
Thank you for everything you have done🙌
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];
Solved this questions along with Regular Exapression matching, all on my own, All thanks to you Striver!!!
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;
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.
Understood ❤
Done Recursion on my own
So blessed to have teacher like You, Very clean explanation. Thank You Striver
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🔥🔥🔥
Is the code working for everyone in leetcode? If yes please share the code. I'm not getting all the test cases passed.
just sawp the strings at the beginning and try again
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
I think we don't need nested loop for *,
for(let j=1; j
Completed DP on strings successfully!!
Thankyou so much for great explanation Striver
Understood!!, and solved this question before explanation, Thanks for such series !!
Understood
This is legit insane! Gold Content.
1st Hard Problem on my own. All credits to you!
You made DP feel like a cup of coffee ☕️ ...
Awesome explanation, I missed the all stars base case while solving on my own,
US
for base case In C++ we can also do
for(int i = 1; i
Thanks Striver. Understood.
Why have you done bitwise or (|) instead of logical or (||) for asterisk case?
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.
@@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).
greatful to u
dp[0][0]=1;
for(int i=1;i
thank you so much striver...................... First time in my life i understood tabulation and able to write code by myself. thankyou so soooooooooooo muchhhhhhhhhhhhhhhhhhhhhh.
Understood !
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.
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"
61% done bro thankyou so much ....
Amazing explanation! Understood!
Wrong Answer
276 / 354 testcases passed
Input
s =
"aab"
p =
"c*a*b"
Use Testcase
Output
false
Expected
true
same with me did you got the solution ?
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
just saw the recursion and rest is super super simple
"Understood"thank you!
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
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
For the base case, couldnt you just write ,
for(int i=1;i
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.
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].
Amazing !!! explanation and energy. Thanks for the content ❤
Did space optimization on my own in a different way...Thank u for this series.
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.
Understood. Thankyou Sir.
fails for test case
pattern = "*"
text = "aa"
You are one of the most successful and disciplined persons I have known in my life.
Just wow 😮 understood 👏❤️
Understood thank you so so much.
Thank You Striver you made the DP journey so Easy...God bless you
understood bhaiya
Thank you Striver Sir, because of all the previous videos and how good you taught us DP, I myself tried the question myself, before seeing your video and my solution worked in first go.
This is a great achievement for me to solve a problem that is of Hard level in Leetcode.
Thank you sir
same with me, striver is GEM
BESTT TEACHERR EVERR!!!
I was able to solve the question and pass 80% of test cases by myself, which was possible only because of you. Understood
Understood ! This Guy is making videos at 4 am !! Crazy
can we run a loop when pattern[ i ] == ' * ' and return accordingly
Instead of using two 1-D Arrays we can further space optimize it using a single array. For every index we require value of it's prev row and prev col if char matches and if it does not match we require prev row same col and same row prev col. We just have to maintain a variable that can store prev row prev col value and have to update it accordingly.
@sarthakyadav9950 can u pls paste the code here , i tried but it is failing for "a" and ""
this ques and regex ques are completely different, dont confuse b/w them
Understood completely
"Understood"
Probably the best playlist on Dp.. Keep going Bhaiya::))
what will happen if * or ? are in s2 i am not understanding how that case is considered
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
amazing ❤
I got it. hats off for space optimization. 👌
understood!!. thank you
base case in tabulation for this condition (i>=0 && j
understood ....this time i skip the optimisation of tabulation method
Understood !!
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🤩.
Gives an error for pattern="*" and text="aa"