for better understanding the 3 formula derivation, imagine moving backwards on String and Pattern with two pointers i and j respectively: - if we hit . , move both pointers back, i - 1 and j - 1 (since we consume these two inputs) - if we hit char match, move both pointers back , or consume both inputs - if we hit mismatch of char, return false - if we hit * (do this recursively until point 3 breaks it ): - if previous char in pattern is same as current character or p[ j-1 ] == s [ i ] , consume string i.e. i -1 - if previous char in pattern is a . , consume string' char : i -1 - if str[ i ] != pattern[j-1] , or we have no occurrence of char in string anymore consume the "char *" pattern (move j-2) check if that is match at any point if you reach start of both pattern and string, its a match!
@CostaKazistov
2 жыл бұрын
yes - moving from the end makes it easier to understand this problem 💯
@sankethb.k642
4 жыл бұрын
If pattern is ".*" it can match with any given string because ".*" means "......." any number of times you want and each single "." can match a single character of the string
@paulifea7072
2 жыл бұрын
thanks for clarifying this. I was wondering why "ablmy" matches "a*b.*y". I assumed ".*" was only allowed to match zero or more instances of a specific character.
@javadoctor101
6 жыл бұрын
In some of his other vidoes he definitely doesn't touch the intution behind dp logic but he DID in this one. He clearly outline the substructure of the problem ie 1) if current char matches we are good 2. If current char doesn't match , no hope 3). if it's *, here's the crux of dp kicks in: 3.1) first sub structure will come when we DO NOT count the char before * ( we have the memoized result for that in i,j-2) 3.2) second sub structure will come when when 3.1 is false and do rely on the char before * ( we have memoized the result for that in i-1,j-1) Imo, he clearly explains above points and that's what is DP all about.
@SritamNanda-x5h
4 ай бұрын
hi doc
@卡机不
4 жыл бұрын
This video is the Most clearly about regex matching i've ever seen
@effy1219
7 жыл бұрын
we are so lucky to have you here :)
@Iamreallyup
6 жыл бұрын
It's the best explanation I found about regular expression matching so far!!!
@tomarintomarin9520
3 жыл бұрын
You know you will understand the problem when lord and savior Roy has a video about it, and thank you
@swathiupadhyaya8812
5 жыл бұрын
Thank you so much for the detailed explanation and for talking about the intuition behind the DP formula. Helped me a lot!
@harshshah5647
4 жыл бұрын
Great Explanation !! Lucky to have a great tutor like you in 21st century !!
@harshpanwar1550
2 жыл бұрын
Tushar Sir🙇♂🙇♂🙇♂🙇♂ Tremendous respect for u🙏🙏🙏🙏🙏🙏
@dmitryrusakov4151
5 жыл бұрын
Actually, we must iterate starting from int i = 0 in the first for loop since empty text matches the pattern like "a*b*". The current code will not handle properly the patterns where Kleene star is at the beginning like, for example, "a*".
@sumeetbisen9708
3 жыл бұрын
But he has already dealt with that in the upper for loop no?
@reubenkuhnert6870
8 жыл бұрын
Hell yeah dude! Been waiting for you to do this one. I haven't had a favorite show since 'sonic the hedgehog' when I was a kid, but I love this show! OMG. Rock on Tushar!
@preety202
4 жыл бұрын
This reminds me of my school in India where professors just tell you the solution and you have to remember. No need to develop thinking ability.
@aditya234567
4 жыл бұрын
where r u now?
@lostgen36
4 жыл бұрын
If your thinking ability is so great, just stop the video after hearing the question explanation and solve it on your own. We need to understand the solution process. Dp is hard enough as it is.
@preety202
4 жыл бұрын
Lost Gen you understand even if you are asked the same question, you will have explain the thinking process behind the solution else you won’t clear the interview.
@harshupreti1526
3 жыл бұрын
@@aditya234567 in india itself XD
@professorpoke
Жыл бұрын
Imo he explained the topic really well.
@jinny5025
4 жыл бұрын
I just subscribed to your channel. I recently started to solve leetcode and videos you uploaded here are all helpful for me to fully understand. Thank you so much!!
@MrThepratik
3 жыл бұрын
Still relevant to date after watching multiple videos on this topic!
@rajusharma9938
4 жыл бұрын
Very nice, great to get a video with great explanation, While submitting this code on leetcode one of the test case is getting failed, which is with text : "aa" and pattern "*a" this should be invalid test case but still leet code is checking this case as well just we need to add a check that if(pattern.length>0 && pattern[0]=='*') { return false; }
@WokieRookie
2 жыл бұрын
Hey Tushar, Thanks a lot for explaining it so clearly and being precise with your solution.
@funsideofthelens
Жыл бұрын
Thanks for the post, Tushar, its still helping folks years later. It would be great, tho if you could clarify the part of the algorithm which populates the first row of the matrix. Of course in this case, the first row is false - none of the pattern can match an empty string, because the first character of the pattern is a literal (vs a Kleene star). However, if you had a pattern like `a*b*` then the entire first row would be true.
@peregrine17
Жыл бұрын
The same thing came into my head also. Good question.
@xuelianwang5300
7 жыл бұрын
Thank you so much, Tushar! You make it so easy to understand!
@Marco-sj5lg
5 жыл бұрын
You never explained how did you came out those induction rules. It makes your tracing meaningless and hard for me to understand (well I understand, but how you came out those induction rules?!). The most difficult part in DP is to figure out those induction rules.
@integralCalculus
5 жыл бұрын
He does explain the recurrence relations reasonably well. Watch 2:49 to 4:32
@8Trails50
5 жыл бұрын
Don't come here for the "why". He never explains why. he only explains the mechanics. I use him for verification.
@hjkc6000
5 жыл бұрын
This man’s videos save me so many hours. I appreciate it.
@8Trails50
5 жыл бұрын
To answer a solution to your problem. Try solving the problems recursively first
@rohan8arora
5 жыл бұрын
@@8Trails50 I agree. But he seems to be one of the few guys who is uploading explanations. Starting with bottoms up usually is not very intuitive.
@yunlongguo4979
4 жыл бұрын
When the text is "aaa" and the pattern is "ab*a*c*a ",the value the matrix return is 0.But in fact , the result is true.The matrix is 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
@rushikmakwawna
3 жыл бұрын
You are right, I am also facing the same issue
@TheGoodboy26
8 жыл бұрын
Thank you so much sir.I really appreciate your efforts for reaching Dp which is a very hard subject and never taught in college. You make it look so simple. Thanks you so much, Regards Aniket Naik,Mumbai.:')
@deddykakunsi
3 ай бұрын
Thank you. Very detail and understandable.
@arghadeep10
8 жыл бұрын
sir ur knowledge on the subject is vast and a great concepts expained videos. THANK YOU SIR VERY MUCH.
@mohysaleh8184
4 жыл бұрын
very clearly explained the DP array logic. well done. have not seen dp used for booleans so this was neat.
@yashmittal6485
4 жыл бұрын
there is a small error in the base case, for the first row there should be condition that if (pat[i]=='*' ) dp[0][i]=dp[0][i-2];
@susrandomguy
Жыл бұрын
It is my second comment on this video. I am amazed how good this explanation is.
@marspark6351
Жыл бұрын
One issue I see with this implementation is that it doesn't consider the cases with bad input. One bad input that can be done that I notice is when "*" is not preceded by a letter. For example, Text: a Pattern: * This makes the program crash instead of failing gracefully because it tried to access an array T[i][j-2] where j == 1. So you'd probably want to check that the first character of "pattern" is within the bounds of an alphabet or "." And if the check fails, then return false since our return type is boolean. Bonus points would be mentioning that instead of returning a boolean, it would be better to return an int that represents true or false along with other error cases such as this one being "INCORRECT_INPUT_ERROR" Or alternatively, you can pass the inputs to another function that checks the validity of the input first
@SandeepParmar22
5 жыл бұрын
Good explanation. Just one comment the index for first for loop must start from 2 and not one because in case pattern contains first character as * , this will access an index t[0][-1] which will fail
@susrandomguy
Жыл бұрын
still one of the best explanation out there.
@tamannaoberoi5757
6 жыл бұрын
It would be of great help if you could help us understand your thought process for deriving the dynamic programming equations.
@vivekgupta1549
7 ай бұрын
what an explanation to a really hard question.
@sanke7982
6 жыл бұрын
Just awesome Tushar!! For the professionals like us, who hardly get some time to ponder over a problem, your videos are great.
@wentaoqiu4072
4 жыл бұрын
I am glad to see many people in the commend section mentioning you didn't explain the why, and jump to how, I guess I will come back for verification.
@ДенисПрошкин-г1м
3 жыл бұрын
Четкое объяснение (первый раз не понял из-за плохого знания английского) Спасибо!
@nishantmiddha9161
4 жыл бұрын
It is important to mention that when you code this problem - there will be OR condition when pattern[j] == '*' i.e T[i][j] = T[i][j-2] | T[i-1][j]
@akarkessel
7 ай бұрын
I solved this problem on leetcode, but for me it has been much easier figuring out the pattern and the rationale by myself other than understanding this video
@haoyang4849
3 жыл бұрын
There is a problem in the nested loop of the JAVA code. It should be for (int i = 1; i
@AGENTxxFURY
3 жыл бұрын
Tushar sir please make comeback to your channel , you are awesome and we all love your videos..!!! :)
@mrzhang2150
5 жыл бұрын
非常喜欢看你的视频,讲的非常仔细。 Very well explained. Thank You!
@천동영-q5y
2 жыл бұрын
as always, crystal clear..
@ashishjadhav7313
7 жыл бұрын
code in the video and on GitHub does this for (int i = 1; i < T.length; i++) { for (int j = 1; j < T[0].length; j++) But both for loop should have conditions either ( i
@xuelianwang5300
6 жыл бұрын
pattern[0] won't be '*', according to leetcode, " '*' Matches zero or more of the preceding element". So there is always at least one character before '*'. if (pattern[i-1] == '*'), the smallest value of i is 2. Therefore i-2=-1 won't happen.
@goutamkundu6392
6 жыл бұрын
In the 2nd case he could have started the loop right at i=2
@DebdattaKundu
5 жыл бұрын
Hi Tushar, Great video! Thanks for sharing and you really clarified the induction rules for generating the DP table. However, I have one comment. The line where you check for a '*' may need a little modification as it fails for one testcase : String = "aaa" Pattern = "ab*a*c*a" Modified piece of code : else if(p.charAt(j-1) == '*') { dp[i][j]=dp[i][j-2]; if(!dp[i][j] && (s.charAt(i-1)==p.charAt(j-2) || p.charAt(j-2) == '.')) { dp[i][j]=dp[i-1][j]; } } Please let me know if this makes sense!
@Poutine-StJean
2 жыл бұрын
Thks! I was stuck on this error.
@ayushbehl7827
5 жыл бұрын
Really , the best explanation for this topic.Thanks man
@md.manikhossain2913
4 жыл бұрын
Hi @Tushar Roy, there is some misconception in your concept while you are initializing 0th row and column. 0th row all should be zero but 0th row should be like this if (p.charAt(i - 1) == '*') dp[0][i] = dp[0][i - 2]; else dp[0][i] = false ;
@paulifea7072
2 жыл бұрын
I thought so too, I tried adding the else statement and it failed some of the test cases I had. Removing else statement passed all test cases online. I have no idea why this is the case because it should not have altered the result in dp[0][0]. I'm still trying to figure this out
@galadesonne5643
2 жыл бұрын
Thank you! Perfect explanation!
@suranaajit123456
3 жыл бұрын
The space complexity O(size of string*size of RE) can be reduced to O(2*size of RE) by preserving just 2 rows.
@natiatavtetrishvili3108
3 жыл бұрын
Thanks for a great explanation 💡
@chetanpatteparapu7600
4 жыл бұрын
Man you're gold. Thanks for the videos
@idiot7leon
4 жыл бұрын
Very clear explaination! Thanks!
@freethinker977
3 жыл бұрын
Brilliant explanation. Thank you. May you please explain how you approach such a problem for the first time you see it? Everything makes sense and simple once you explained it, but how do you for example have all '*' cases covered? How you know you heat all of them?
@pumpkinswang9758
7 жыл бұрын
Thanks for your explanation!!!! Makes so much sense to me
@c0411026
3 жыл бұрын
Great video, thanks!
@praveenchaudhary235
6 жыл бұрын
I always prefer watching your videos for explanation of algos.
@kevinli9331
8 жыл бұрын
I'm a little confused that why "ablmy" matches "a*b.*y"? What does the character "."represent here?
@akshatpokhriyal3214
8 жыл бұрын
ablmy doesn't match the regex. If you take "l" for "." in regex, then it has to be one or more occurrences of "l". .* means 0 or more occurrences of any character, but, any one character. It can't be 0 or more occurrences of two different characters. Make sense?
@akshatpokhriyal3214
8 жыл бұрын
Or, does it mean that X.*Y is equivalent to XY, X.Y, X..Y, X...Y, .... so on. And then each "." can be replaced with a different character? It doesn't necessarily have to be the same...
@45santanu
6 жыл бұрын
This is correct
@boqigao2242
3 жыл бұрын
@@BarikZone Thank you so much!!! That's a super clear answer!
@shomalochona8403
6 жыл бұрын
Thank you so much! Your videos are so clearly explained!
@sanyamsinghal7992
4 жыл бұрын
Thanks for this great explanation
@babulbhanu8213
4 жыл бұрын
thanks a lot brother, you made life easy for us really appreciate your hard work
@yunlongguo4979
4 жыл бұрын
I ' ve got a lot from your show !thank you!
@PriyankaSingh-pn8xv
3 жыл бұрын
Clearly explained, thanks
@brozuh2364
5 жыл бұрын
The best explanation for leetcode 10. Stongly recommended.
@vamsik6457
7 жыл бұрын
Thanks a lot for amazing and clear explanation.
@ganeshd2040
8 жыл бұрын
Excellent video Tushar.. I think you can add below check - As soon as you are done with outer for loop, if T[i][i] = false then exit with result as false. I believe if at any point of time if that diagonal value is false then there is no point continuing as for sure its going to be false for rest of the text. Though it defeats the purpose of dynamic programming, its a good point to mention it to the audience or interviewer :-). Also could you please provide your leetcode profile name if you are out there and active?
@emmettz6729
3 жыл бұрын
I think his explanation about when pattern is "xa*" and text is "xa" is not as easy as understandable as others but overall this video is great.
@ktslwy
6 жыл бұрын
Very well explained. Thank You!
@glassfox6046
6 жыл бұрын
This doesn't really explain the intuition behind the problem. This is more of going through steps of a solved problem mechanically without showing the insights that led to this method of solving the problem.
@poojanarayan9503
6 жыл бұрын
Agree. One should first make the matrix with their own decision making and then see how "T" propagates. That would be a generic way of solving any such question. It's hard to remember these equations.
@vanyastaleva415
6 жыл бұрын
Oh, come on. He explained everything. Watch it again and listen carefully. For me the "*" took a little time to understand how do we decide the T[i][j] value for it, but he explained it well. Also the code shows the idea.
@akshaybhatia3611
6 жыл бұрын
true, to learn dp the best approach is : 1) see if the problem is recursive in nature. if yes : solve recursively else try some different approac(LIS for eg is a dp problem which is not recursive in nature) after solving recursively , see if there are overlapping subproblems building a recursive tree. apply memoization also known as top down DP. this will make ur solution really fast. to further optimize it, think iteratively using tabulation also known as bottom up dp to remove the recursive call overhead. after enough practice you will be able to jump directly on bottom up rather than top down
@himanshuchhikara4918
4 жыл бұрын
well played mr gambir
@aksmehrotra1
7 жыл бұрын
You are the best. thanks for the best explanation!
@zeyuwu8703
4 жыл бұрын
very appraciative for this explanation~
@rogerwhite8061
6 жыл бұрын
Wow this is unbelievable, thank you
@prahladsingh9132
8 жыл бұрын
Interesting.. finally into automata !! keep up thr good work !!
@ankuwagh
8 жыл бұрын
Best Explanation. Thank You!
@pramodchoudhari3676
3 жыл бұрын
1.i think we should not initialize the first row as false blindly 2.the first row should be initialized as follows for(int j=2;j
@algorithmicthoughts8565
8 жыл бұрын
Tushar your videos help quite a lot .. Thank you very much . Keep doing this. I Would like to make a request to you if you can have a video on Treaps it will be really helpful. Thanks in Advance.
@ManishKumar5
8 жыл бұрын
+1 for treaps.
@nanyang3728
8 жыл бұрын
Thank you for your sharing, very helpful
@sahil-7473
5 жыл бұрын
What about if string is 'aa' and pattern is 'a*' ?
@high-oncode7576
3 жыл бұрын
true
@larry1285
6 жыл бұрын
Thanks for the tutorial. I learned a lot
@arghadeep10
8 жыл бұрын
SIR YOU ARE AN EXPERT ON ALGORITMS.
@zhangwei8986
7 жыл бұрын
Hi Tushar, thx a lot for your explanation. For this line: T[i][j] = T[i][j] | T[i - 1][j], you only mentioned why do we use T[i-1][j], but in what situation will we use T[i][j]? Thx!
@physcho1231
7 жыл бұрын
Thats because there maybe conditions where 0 occurances scenario is true hence setting T[i][j] as true. After that, checking for 1 or more occurances is not required. If T[i][j] is already true due to 0 occurances scenario, here in the code he is doing OR operation to retain the true value of T[i][j] irrespective of the result of check of 1 occurances or more.
@vanyastaleva415
6 жыл бұрын
If you look at the code closely, T[i][j] has been set several lines before to match T[i][j-2] . In the text "x" and pattern "xa*" you check the value T[i][j-2] (the value for comparing text "x" and pattern "x". You remove two characters from the pattern (the "*" and the previous character) and check if this is true or false).Then you check the other condition for the previous character of the pattern to either be "." or match the current character of the text. If either of the two conditions is true, then you get true for T[i][j] too. So the line " T[i][j] = T[i][j] | T[i - 1][j]", translates as T[i][j] = T[i][j-2] | T[i - 1][j].
@zhangyaokun5046
5 жыл бұрын
Thank you so much, really clear and helpful.
@SL-tg6mv
3 жыл бұрын
thank you for such a great work!!
@oldcoolbroqiuqiu6593
7 жыл бұрын
Man, You saved my algo. Thanks a lot!
@capy_can_code
4 жыл бұрын
amazing man! simply too good! cheers :D
@learnwithgames7994
6 ай бұрын
Thank you sir
@polavenki
7 жыл бұрын
You killed it. Awesome.
@subhadipbhattacharyya2296
4 жыл бұрын
i am little confused with the code.i can see that the 0th row getting set but what about 0th column?
@贺剑嵩
6 жыл бұрын
try str="aa", pattern="a*", the code shown in this video failed to the correct result.
@vical1063
6 жыл бұрын
It worked in my case, you probably forgot the first loop.
@tonyjiang4991
4 жыл бұрын
I am not being picking, just help pointing some errors, the vedio was in general good. But there was an implemenation bug in the code. (1) Line T[0][i] = T[0][i - 2] will access array out of range if i =1.
@cantwaittowatch
5 жыл бұрын
I have a question in regards to the pattern: xa* and string: xaab. Result of the value is False. I think it should be True based on the examples mentioned at 0:32 where for * this expression is considered true, that is b,ab. The rationale for being true is, if you take a* as that which encompasses aab, then it should be true, isn't it? According to the equation, it's right but the value put in is wrong as it takes the false and not true value!. I wanted to add some more details here for clarification: take an example as per the clip, 0:32, where the pattern is a*b and the string is b,ab - last b in the pattern and string match, which leaves us with b,a mapping to a* - if this is said to be true, which means string can contain any chars and not just a's..
@cantwaittowatch
5 жыл бұрын
I'll reply to my own discovered answer - I found this after a detailed trace of the code, and the answer is False but I don't think the code sets it explicitly (as seen in the case of the else condition), but the default value is false. Another observation I came across was that the code in the block that checks for '*' also checks for '.' and one of the statement it assigns is T[i][j] - I didn't see any case where this gets exercised!
@RageshRajagopalan
5 жыл бұрын
An invalid pattern like "*a" will give ArrayIndexOutOfBoundsException at the 0th-row initialization. Thanks for the video!
@lavenderzhong4091
7 жыл бұрын
very clear! thank you so much
@薛亮-w3j
4 жыл бұрын
Well explained, thanks a lot~
@ParadiseQ
3 жыл бұрын
For this algorithm, what I don't understand is why s = "abc" matches p = "a .*". We know "ab" matches "a.*", so DP(i-1, j) is True. Since s[i] == "c" matches p[j-1] = ".", we should check DP(i-1,j) || DP(i,j-1). This gives True since DP(i-1, j) is True. So DP(i, j) = True, which means "abc" matches "a .*". I am so confused.
@sabeernitb
8 жыл бұрын
thanks again Tushar!
@niels564
7 жыл бұрын
Great explanation!
@p111calcutta1
6 жыл бұрын
Hi tushar, how do you make sure this code wont crash when say i=1 , index of array will be -ve (i-2) //Deals with patterns like a* or a*b* or a*b*c* for (int i = 1; i < T[0].length; i++) { if (pattern[i-1] == '*') { T[0][i] = T[0][i - 2]; } }
@krishna0908
6 жыл бұрын
Thanks Tushar!
@yfanxie580
4 жыл бұрын
when some Indian guys on youtube are better than your teacher at college.
@divanshuabhishek3733
4 жыл бұрын
well that Indian guy is working in Apple, while your teacher is not XD
Пікірлер: 285