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 🙌 🙌
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
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 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😊
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.
I could have never thought that I could solve a Leetcode hard question by myself. This dp playlist is the best playlist in UA-cam and I thank you Striver for such an amazing playlist.
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 _/\_
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
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 ❤!
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.
*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
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 !!!!
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 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];
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 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;
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
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
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).
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.
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
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"
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.
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].
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🔥🔥🔥
thank you so much striver...................... First time in my life i understood tabulation and able to write code by myself. thankyou so soooooooooooo muchhhhhhhhhhhhhhhhhhhhhh.
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
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.
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.
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.
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 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.
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....?
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,
me too
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
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 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?
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😂😂🥲
DP on strings understood ✅
From hating and fearing DP to love doing it.. all the way grateful to you.
I could have never thought that I could solve a Leetcode hard question by myself. This dp playlist is the best playlist in UA-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
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
I was able to think of almost the whole approach without watching your explanation. Couldn't be more grateful!
Base Case for Tabulation
dp[0][0]=true;
if(pattern[0]=='*')
{
int i=1;
while(i
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
We can make the base case simpler
if(ind1
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 ❤!
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 !!
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.
*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
😏😏😏😏😏😉😏😏😏😏😏
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 !!!!
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 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];
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 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;
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
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
Done and dusted in the DP revision :)
(31 mins)
Nov'17, 2023 10:11 pm
US
for base case In C++ we can also do
for(int i = 1; i
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 ?
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
On Leetcode : only 1731/1811 passes in the bottom up (tabulation) apparoch
"*a?b*"
""zacabz" This testcase fails for some reason
Understood the entire DP on Strings. Thankyou so much for the quality videos !!!!!!!!!!!!
+1
@@ani68 found the legend aniruddha :)
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).
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.
Understood the entire DP on strings, thanks a lot!
UNDERSTOOD.....Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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
dp[0][0]=1;
for(int i=1;i
Understood
It was great learning DP on strings from your striver🙌🙌
Thank you for everything you have done🙌
Understood. Now I am able to make logic and intuition behind the question. Thanks Striver
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"
Understood ❤
Sir Hatts Off to you, Keep Going...
#Understood | Wonderful series of DP on strings | Definitely feeling confident !
Approach to this problem is explained well, and optimizations are interesting to perform.
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
"UNDERSTOOD BHAIYA!!"
Bro , I literally enjoyed this lecture, I am filled with joy , Awesome explanation
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.
For the base case, couldnt you just write ,
for(int i=1;i
Done Recursion on my own
greatful to u
Understood !
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].
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🔥🔥🔥
Solved this questions along with Regular Exapression matching, all on my own, All thanks to you Striver!!!
can we run a loop when pattern[ i ] == ' * ' and return accordingly
thank you so much striver...................... First time in my life i understood tabulation and able to write code by myself. thankyou so soooooooooooo muchhhhhhhhhhhhhhhhhhhhhh.
61% done bro thankyou so much ....
So blessed to have teacher like You, Very clean explanation. Thank You Striver
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
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.
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 ""
Understood
This is legit insane! Gold Content.
1st Hard Problem on my own. All credits to you!
base case in tabulation for this condition (i>=0 && j
fails for test case
pattern = "*"
text = "aa"
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.
Understood!!, and solved this question before explanation, Thanks for such series !!
Completed DP on strings successfully!!
Awesome explanation, I missed the all stars base case while solving on my own,
Thankyou so much for great explanation Striver
this ques and regex ques are completely different, dont confuse b/w them
You made DP feel like a cup of coffee ☕️ ...
what will happen if * or ? are in s2 i am not understanding how that case is considered
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
Amazing explanation! Understood!
Amazing !!! explanation and energy. Thanks for the content ❤
What if the second string is : "abcbdef"? Will this solution work for this test case also?🤔
Gives an error for pattern="*" and text="aa"
just saw the recursion and rest is super super simple
"Understood"thank you!
Understood. Thankyou Sir.
Understood thank you so so much.
BESTT TEACHERR EVERR!!!
use i for text and j for pattern easier space optimization
Just wow 😮 understood 👏❤️
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.
I have a doubt.. should it be this '|' or '||' , for or sign
Understood completely
Inspite of this code to check for the base case s2 is empty and s1 contains '**...' or not .
for(int i=1;i
can we use for loop in case of *
Did space optimization on my own in a different way...Thank u for this series.
if constraint start from 0 then how to handle those cases
I got it. hats off for space optimization. 👌
Understood! Is this the basis of how regexp match with '*' or '?' is implemented?
understood bhaiya
Till how much optimized is needed in interviews? will they expect space optimized, or , till tabulation is mandatory?
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....?
understood!!. thank you