Hey Tushar, At 10:25 you are comparing "x?y" and "xa which is essentially T[i-1][j-1] but the code on the white-board states that T[i][j] = T[i][j-1] || T[i-1][j]. If pattern[j]=='?' then T[i][j] = T[i][j-1] || T[i-1][j] || T[i-1][j-1];
yup correct. Also not clear in 12:05 "2nd case(considering * as non null character)" why the last character of string is removed but * from pattern is not removed. Anybody?
To get all test cases you need a different initialization for the pattern index. You can initialize it with the previous value on the pattern index if the current letter is a '*' or else false.
I must tell u I failed drastically to understand any DP solution by reading books or online written explanation .. your video has helped me improve drastically . now with ur help i am able to visualise dp based problems
@Vasanthy, T[i][j-1] represents if * is an empty char then you just need to look at previous match result on the left, T[i-1][j] represents if * matches one or multiple chars, then you look at the top, since top already match the current char.
Great explanation Tushar. A clarification here, which I surmise you did, but while tracing of the 3rd row, that is 'y' and 4th column where there is a '*', you mentioned at the tail end to take the true value from T[3][3]. Is it that, if any value is true in either T[3,3] or T[2,4] - then fill the resultant T[3][3] with T? Thanks
why do you need to replace multiple ** into one *? we can just look at the previous T[i][j-1] to check for the first row, i.e. //in the case of "a**b" the T will be all false for (int j = 1; j < T[0].length; j++) { if (pattern[j - 1] == '*') { T[0][j] = T[0][j - 1]; } }
I finally get to understand wildcard matching (and hopefully regular expression soon)!!! This is the lc question that I've been confused for so long time! I'm crying!!! Thank you so much:)
Another awesome explanation!I have a question. I didn't get the part when character is * and you take the value from either top or left. If top and left value don't match , we will get true in some cases and false in others since it's an OR. In your example , if you would have taken false instead of true , final answer would have been different. How does it work?
thanks for the video. well explained. when I first approached the problem I thought how can I solve this without any non-constant space. regular expressions need only constant number of states (finite automata) , hence the use of non constant space is redundant (using extra matrix for dp). can you perhaps show how can this be done this way?
u can keep stars that are seperated by ? or even characters , also if missing subsequence is not possible we can use the multiple stars to combine various subsequence to form missing subsequences
this is some great explanation. could you please introduce the case where there is a special character (say '+') where it matches at least one character of the previous sequence? thanks in advance :)
In the second case, when * is treated as a non-zero sequence we take a value from the top ( T[i-1][j] ) that means * has consumed the i-th character in the string, j still with no change and, as long as I understand, we shouldn't erase * character from the pattern ( ua-cam.com/video/3ZDZ-N0EPV0/v-deo.html ) By the way, want to say thanks to you, Tushar Roy for this video and what you are doing, it is really helpful. Hope to see more videos and tutorials from you.
Why do we need to compute all the values in T[][] ? Incrementing the positions in String and expression till the end using recursion gives the best time complexity ?
Why and how we conclude we need to perform DP at 2:02 sec of video ? How we understand when we need to apply DP ? because DP always optimizations . What's Brute force way ? Guess we need to show that in interview before we jump to DP. Rigth ?
I solved it using recursion and memoization. It is because of this video I have realized my Dynamic Programming is trash. Nice video (I think), I did not actually understand it🥲...I will comeback after solving some medium problems with dynamic programming, hopefully I will get the logic behind.
Hi Tushar , for input , patter= "ab*c" and string= "ac". this algorithm is returning false. though the pattern should accept ac .as it starts with a ends with c and zero occurrence of b. can you please clarify .
I think you are confusing wildcard matching with regular expression matching. The meaning of * is different for wildcard and regex. In regex it means match 0 or more occurrences of the character in front of it, in your example, regex ab*c would match ac. But in wildcard matching, * means 0 or more characters, so ab*c would match a word that contains a, b, c, and have 0 or more characters between b and c, since ac does not contain b, it won't match. Wildcard matching is not the same as regular expression matching, though they sound very similar.
at 15:20 you also have to see the case if the pattern in any number of stars in the begininng. For ex: if pattern is "***a" then the T[0][1], T[0][2], T[0][3] all will be true
Not clear in 12:05 "2nd case(considering * as non null character)" why the last character of string is removed but * from pattern is not removed. Anybody?
Awesome, That's great video. I prefer to keep T[i][j] = T[i][j-1] || T[i-1][j] || T[i-1][j-1] if (pattern[j] == *) without optimization for easy understanding.
Thanks for the great video and the detailed explanation. I have a doubt at point 5:06 of the video. You said pattern * can match with empty string. Then why is T[0][4] False? Should it not be True?
The * pattern can be used to match with 0 or more characters..so in your case for NULL string, if pattern itself starts with * then it it okay..BUT as there is already a pattern BEFORE *, NULL can't match with * as it would theoretically mean that the pattern before * has matched to NULL. Got it?
Example string: "xacyxay" and pattern "x?y" should return True right because the last three characters are a match, but using this approach it returns False. Or should it return False only?
You might be confused because * matches an empty string, however our pattern is not just *. T[0][4] is a match of empty string against the pattern x?y*, therefore it's not a match, so it's false.
All your videos are really helpful.But i did not get the comparison of '*". How '*' replaces that character and if it does then we will compare pattern: x ? y y with text: x a
either * can be used as 0 sequence if that is the case then we get the value from the above cell else if * is used as a sequence > 0 then it means * has been consumed by the current matching so we get the value from the left cell. And the final value is the OR of both the values
in wildcard a* character - any 0 or more alphabet character. - a, ab, aa, ac, aaa in regular a* character - 0 more a character eg- empty, a, aa, aaa, aaaa this one can't be ab
If the star would have appeared at the beginning of the pattern then he would've marked it as true, but for this case, where string = "" and pattern = "abc*" it shouldn't show true!
Thank you very much Tushar, for the excellent video. However, I had a problem with your algorithm. If I implement with 2D array, it can't pass leetcode OJ (says memory limit exceeded). If I implement with 1D array, it says time limit exceeded. I used C++ and didn't see any extra code compared with your java code. Any thought?
Normally while checking if a pattern matches a given input ,we start from left of both input and pattern and move to right till the end by comparing both the input and the pattern. In DP should we think in a different way as if we are comparing from right to left and is this is the reason when you have P[j]=* then we have T[i-1][j] as we are expecting more characters for * in input while moving in left direction. This is to understand DP intuitively as the * matching case is little confusing how it works conceptually.
+Tushar Roy I believe the example that you showed is from right to left itself and hence when p[j]=='*' and for case where there are more * characters you use T[i-1][j] ? Am I right ?
+Tushar Roy Sorry to bother u so much.Thanks for your time. For a string s[0-i] ,I assume 0 to be at left and going from 0 to i meaning moving right and hence i to be at the right. To decide if T[i][j] is a match which means s[0-i] matches p[0-j] you are first comparing the last characters(right most for the given string which ends at i and pattern which ends at j and the based on ith and jth comparision decrementing either i or j or both by one such as T[i-1][j-1] ) 1)if s[i]==p[j] then T[i][j]=p[i-1][j-1] 2)if p[j]=='*' then T[i][j] = dp[i-1][j] for more * sequence || dp[i][j-1] for zero * sequence. If you were comparing the string and pattern from left to right then for a given string s[0-i] and pattern[0-j] you should start comparing from left i.e zeroth positions of both string and pattern and then move towards end i.e right side.Isnt it ?Also if it is left to right ,for a given T[i][j] for the case when p[j]=='*' and when * is a sequence of characters ,you are taking T[i-1][j] ,shouldn't it be T[i+1][j] ? I understand that this DP is a bottom up approach but for a specific T[i][j] you are starting the comparision from extreme right of both string and pattern and moving towards left. I was tring to solve articles.leetcode.com/regular-expression-matching/ through DP and couldnt understand how to use DP to match * which means 0 or more of previous character and came across your explanation.
The example mentioned initially is incorrect. For a pattern, a*b, a string "b" should be a match as we are looking for a string with 0 or more "a"s followed by a b. Otherwise a good video.
x.y*z is not Equal to xaylmz. Because of in Expression y is occure n times including NUll but in String after y->lm is Encounter . So my Question is How * match lm ?
Thanks for the video. The solution seems to work fine. However, I would really appreciate if you could comment/explain on how you arrived at this solution. (The usual way to solve this would be to do a character-compare across two strings and use an additional loop for '*' character. That may / may not be the best solution. This would actually avoid a 2-D array and O(mn) complexity... instead it would be O(m) or O(n) right?. But not sure how/why I would arrive at the solution in the video)
Hi, thanks for your video. It's the same excellent. Can I ask one question? Why do we need T[0][0], since there is no [0] letter in neither string nor pattern? Thanks.
@@kitther It would be harder to initialize T. i.e String:adc pattern: *a*c, When it comes to T[0][1], that's when you considering if a and *a is a match, you would want to refer to T[0-1][1] or T[0][1-1] according to the algorithm provided. Obviously referring to T[-1][1] would result in intdexOutOfBoundary exception. So you need to consider T[0][1] alone and initialize it and it would be harder. The initialization with empty char in the beginning would be a lot easier, you just have to make '*' match empty char that'll work.
@@addiegupta '?' can be replaced with any character. Let's say we replace it with 'a'. And '*' means zero or more repetition of previous character. Let's take zero repetition of 'y'. That leaves is with 'xa'.
+Tushar Roy Thanks for the great video! For regex, the algorithm will remain same apart from some conditions (example - for regex a* - while matching the patter I need to go back 2 columns and check if condition True is possible or not), right?
if (writeIndex > 0 && pattern[0] == '*') temp[0][1] = true; } +Tushar Roy please clerify : why we are not taking pattern[1]== '*' instead of looking for index 0. As index 0 is always a empty.
Means index 0 always represent a empty character. So patter[0] contains null. So why we are checking patter[0]=='*'. Shouldn't we instead check pattern[1] == '*' please check at 5.08
Thanks to all Indian guys on UA-cam, I'm a well-paid software engineer!
yo wtf have u posted in yur channel man like wtf?????
Hey Tushar,
At 10:25 you are comparing "x?y" and "xa which is essentially T[i-1][j-1] but the code on the white-board states that T[i][j] = T[i][j-1] || T[i-1][j].
If pattern[j]=='?' then T[i][j] = T[i][j-1] || T[i-1][j] || T[i-1][j-1];
yup correct. Also not clear in 12:05 "2nd case(considering * as non null character)" why the last character of string is removed but * from pattern is not removed. Anybody?
He mistakenly removed the '*' character but explained correctly....comparison should be in x?y* and xa.
To get all test cases you need a different initialization for the pattern index. You can initialize it with the previous value on the pattern index if the current letter is a '*' or else false.
thank you so much for this comment
I must tell u I failed drastically to understand any DP solution by reading books or online written explanation .. your video has helped me improve drastically . now with ur help i am able to visualise dp based problems
can we match empty string ( ' ' ) with * ( because * also match 0th string)..??
10:44 - we shouldn't wipe "*" in the explanation part?
totally agree...this is most trickiest part of the algo.
@Tushar: Pls add that explanation if possible.Thanks in advance.
@Vasanthy, T[i][j-1] represents if * is an empty char then you just need to look at previous match result on the left, T[i-1][j] represents if * matches one or multiple chars, then you look at the top, since top already match the current char.
Correct , thank god you raised this concern
@@dy0953 what does "since top already match the current char" mean?
@@dy0953 what does "since top already match the current char" mean? please tell about it
7 years OLD still GOLD
The case for the star where you examine T[i-1][j], is that assuming the star matches the character at i and you are seeing if it matches more?
Yes, it should be explained in this way. Otherwise, it should be T[i-1][j-1] if we follow the explanation from author, which however is wrong.
Thanks for the videos, please keep making them. Will recommend to all my friends~
The only video I have watched so many times at different stages of my career(*pure gold*).
Wow... There is a sort of beauty in dynamic programming.
Thanks a lot. I understand when i see the picture.
Great explanation Tushar. A clarification here, which I surmise you did, but while tracing of the 3rd row, that is 'y' and 4th column where there is a '*', you mentioned at the tail end to take the true value from T[3][3].
Is it that, if any value is true in either T[3,3] or T[2,4] - then fill the resultant T[3][3] with T?
Thanks
For case 2:
Matching the pattern this way might help in understanding --
b a *
b a
or
b a *
b a
Your videos help me a lot! I just want to say thank you!
why do you need to replace multiple ** into one *? we can just look at the previous T[i][j-1] to check for the first row, i.e.
//in the case of "a**b" the T will be all false
for (int j = 1; j < T[0].length; j++) {
if (pattern[j - 1] == '*') {
T[0][j] = T[0][j - 1];
}
}
your energy level is on another level
I finally get to understand wildcard matching (and hopefully regular expression soon)!!! This is the lc question that I've been confused for so long time! I'm crying!!! Thank you so much:)
Wow! Explanation was super simple and clear. Thank you so much tushar****
As usual excellent work Tushar! You rock man! Keep continuing the good work buddy!
Another awesome explanation!I have a question. I didn't get the part when character is * and you take the value from either top or left. If top and left value don't match , we will get true in some cases and false in others since it's an OR. In your example , if you would have taken false instead of true , final answer would have been different. How does it work?
thanks for the video. well explained.
when I first approached the problem I thought how can I solve this without any non-constant space.
regular expressions need only constant number of states (finite automata) , hence the use of non constant space is redundant (using extra matrix for dp).
can you perhaps show how can this be done this way?
Is it necessary to convert multiple stars into one or can we keep them as it is ?
u can keep stars that are seperated by ? or even characters , also if missing subsequence is not possible we can use the multiple stars to combine various subsequence to form missing subsequences
Can be further optimised by using boolean T[][]=new boolean[string.length+1][writeIndex+1]; and changing (int j=1;j
this is some great explanation. could you please introduce the case where there is a special character (say '+') where it matches at least one character of the previous sequence? thanks in advance :)
It's explained here: ua-cam.com/video/l3hda49XcDE/v-deo.html
Brilliant explaination sir❤
In the second case, when * is treated as a non-zero sequence we take a value from the top ( T[i-1][j] ) that means * has consumed the i-th character in the string, j still with no change and, as long as I understand, we shouldn't erase * character from the pattern ( ua-cam.com/video/3ZDZ-N0EPV0/v-deo.html )
By the way, want to say thanks to you, Tushar Roy for this video and what you are doing, it is really helpful. Hope to see more videos and tutorials from you.
BEST WILDCARD MATCHING EXPLANATION EVER.
Clear and concise explanation!
What an awesome explanation!
This video is crucial for dynamic programing tabulation approach - Thank you Tushar
tushar sir u r making our path easier
sir if there is * in pattern then we should check left, upside and 'DIAGONALLY' also otherwise some test cases will be failed
I was also thinking about same.
if you match * with "a" then this will fail.
@@vivek5562 * and "a" should match and if u follow this algorithm it does match. It doesn't fail.
Excellent explanation
Great explanation. Thank you.
Thank you so much for a such great explanation
Great explanation! Thanks for the help!
Very easy way of explanation , thanks.
Why do we need to compute all the values in T[][] ? Incrementing the positions in String and expression till the end using recursion gives the best time complexity ?
At 1:11 for pattern a*b string abc, why for this case it is false. * means there could be zero characters.
Can you please explain this?
Why and how we conclude we need to perform DP at 2:02 sec of video ? How we understand when we need to apply DP ? because DP always optimizations . What's Brute force way ? Guess we need to show that in interview before we jump to DP. Rigth ?
Wow, excellent explanation!
I solved it using recursion and memoization. It is because of this video I have realized my Dynamic Programming is trash. Nice video (I think), I did not actually understand it🥲...I will comeback after solving some medium problems with dynamic programming, hopefully I will get the logic behind.
I am unable to understand when there is * mark what to do?
Can we extend this logic to contain a delimiter character say '/' whose first instance does not map to '*' of any character ?
All your videos are awesome.. You are the best teacher.
11:27 - Very important part on the video
why is their difference in regex and wildcard solution for pattern[i-1] = '*' for 0 occurance of character before '*'?
Hi Tushar , for input , patter= "ab*c" and string= "ac". this algorithm is returning false. though the pattern should accept ac .as it starts with a ends with c and zero occurrence of b. can you please clarify .
I think you are confusing wildcard matching with regular expression matching. The meaning of * is different for wildcard and regex. In regex it means match 0 or more occurrences of the character in front of it, in your example, regex ab*c would match ac. But in wildcard matching, * means 0 or more characters, so ab*c would match a word that contains a, b, c, and have 0 or more characters between b and c, since ac does not contain b, it won't match. Wildcard matching is not the same as regular expression matching, though they sound very similar.
false is expected answer as string "ac" doesn't have 'b' char which is required by pattern.
Good Explanation Tushar!!
at 15:20 you also have to see the case if the pattern in any number of stars in the begininng. For ex: if pattern is "***a" then the T[0][1], T[0][2], T[0][3] all will be true
Amazing thank you
Not clear in 12:05 "2nd case(considering * as non null character)" why the last character of string is removed but * from pattern is not removed. Anybody?
Awesome, That's great video. I prefer to keep T[i][j] = T[i][j-1] || T[i-1][j] || T[i-1][j-1] if (pattern[j] == *) without optimization for easy understanding.
Thanks for the great video and the detailed explanation. I have a doubt at point 5:06 of the video. You said pattern * can match with empty string. Then why is T[0][4] False? Should it not be True?
First try to understand what T[i][j] represent, then you will get your answer
The * pattern can be used to match with 0 or more characters..so in your case for NULL string, if pattern itself starts with * then it it okay..BUT as there is already a pattern BEFORE *, NULL can't match with * as it would theoretically mean that the pattern before * has matched to NULL. Got it?
Example string: "xacyxay" and pattern "x?y" should return True right because the last three characters are a match, but using this approach it returns False. Or should it return False only?
? can only be one character. x*y would match this though
Doesn't '?' mean that a is optional rather than "any 1 character between a and b"
Thanks for the great video! Is it correct that this algorithm won't work, if you have wildcards in the front of your pattern?
+Tushar Roy you are right. My initial implementation was wrong
Why t[0][4] is false?
It should be true no?
You might be confused because * matches an empty string, however our pattern is not just *. T[0][4] is a match of empty string against the pattern x?y*, therefore it's not a match, so it's false.
All your videos are really helpful.But i did not get the comparison of '*". How '*' replaces that character and if it does then we will compare pattern: x ? y y with text: x a
either * can be used as 0 sequence
if that is the case then we get the value from the above cell
else if * is used as a sequence > 0 then it means * has been consumed by the current matching so we get the value from the left cell.
And the final value is the OR of both the values
what is difference between regular exp match and wildcard match?? pls explain me.
in wildcard a* character - any 0 or more alphabet character. - a, ab, aa, ac, aaa
in regular a* character - 0 more a character eg- empty, a, aa, aaa, aaaa this one can't be ab
Why null string is not matched withs star in row 1
If the "*" is at the start of the pattern taking it from left or above should fail.
I don't understand about his explanation at 5:02 that * match empty string. However, he wrote F for matrix 0 and *.
If the star would have appeared at the beginning of the pattern then he would've marked it as true, but for this case, where string = "" and pattern = "abc*" it shouldn't show true!
What if a partial match was ok? how would the DP formula change?
Also how do you do it with 1D array?
Yes it is possible with just O(pattern) space complexity. See my solution here: gist.github.com/arunk054/f78091bf5e44ce5386a8035408a08377
Btw.. Nice meeting you again @Kamal. Remember Microsoft 2016?
You don't have to remember whole NxM matrix. You just need to remember the previous value on the left and one row of values above the current row.
Thank you very much Tushar, for the excellent video. However, I had a problem with your algorithm. If I implement with 2D array, it can't pass leetcode OJ (says memory limit exceeded). If I implement with 1D array, it says time limit exceeded. I used C++ and didn't see any extra code compared with your java code. Any thought?
+Tushar Roy Thanks for reply and appreciate if you could take a look. Thanks. tinyurl.com/hrh8qj3
I love you man! :D I wish I could get you a beer
He doesn't drink
Normally while checking if a pattern matches a given input ,we start from left of both input and pattern and move to right till the end by comparing both the input and the pattern.
In DP should we think in a different way as if we are comparing from right to left and is this is the reason when you have P[j]=* then we have T[i-1][j] as we are expecting more characters for * in input while moving in left direction.
This is to understand DP intuitively as the * matching case is little confusing how it works conceptually.
+kk k Also ,if this has to work for right to left,the pattern should be symmetrical ?
+Tushar Roy I believe the example that you showed is from right to left itself and hence when p[j]=='*' and for case where there are more * characters you use T[i-1][j] ? Am I right ?
+Tushar Roy Sorry to bother u so much.Thanks for your time.
For a string s[0-i] ,I assume 0 to be at left and going from 0 to i meaning moving right and hence i to be at the right.
To decide if T[i][j] is a match which means s[0-i] matches p[0-j] you are first comparing the last characters(right most for the given string which ends at i and pattern which ends at j and the based on ith and jth comparision decrementing either i or j or both by one such as T[i-1][j-1] )
1)if s[i]==p[j] then T[i][j]=p[i-1][j-1]
2)if p[j]=='*' then T[i][j] = dp[i-1][j] for more * sequence || dp[i][j-1] for zero * sequence.
If you were comparing the string and pattern from left to right then for a given string s[0-i] and pattern[0-j] you should start comparing from left i.e zeroth positions of both string and pattern and then move towards end i.e right side.Isnt it ?Also if it is left to right ,for a given T[i][j] for the case when p[j]=='*' and when * is a sequence of characters ,you are taking T[i-1][j] ,shouldn't it be T[i+1][j] ?
I understand that this DP is a bottom up approach but for a specific T[i][j] you are starting the comparision from extreme right of both string and pattern and moving towards left.
I was tring to solve articles.leetcode.com/regular-expression-matching/ through DP and couldnt understand how to use DP to match * which means 0 or more of previous character and came across your explanation.
Great work thank you!
is this the same as the regular expression matching dp problem?
The example mentioned initially is incorrect. For a pattern, a*b, a string "b" should be a match as we are looking for a string with 0 or more "a"s followed by a b.
Otherwise a good video.
I'm here because CoPilot suggested this video in an auto-completed comment. (yes really)
How did you derived the formula at 2:04 ?
x.y*z is not Equal to xaylmz. Because of in Expression y is occure n times including NUll but in String after y->lm is Encounter . So my Question is How * match lm ?
ua-cam.com/video/EOWHWVd540U/v-deo.html
Thanks for the video. The solution seems to work fine.
However, I would really appreciate if you could comment/explain on how you arrived at this solution.
(The usual way to solve this would be to do a character-compare across two strings and use an additional loop for '*' character. That may / may not be the best solution. This would actually avoid a 2-D array and O(mn) complexity... instead it would be O(m) or O(n) right?. But not sure how/why I would arrive at the solution in the video)
Thank you it would help a lot to me
Hi, thanks for your video. It's the same excellent. Can I ask one question? Why do we need T[0][0], since there is no [0] letter in neither string nor pattern? Thanks.
It will deal with situation when * represent empty string in the beginning. i.e s:abcd p:*abcd
@@wensun510 I suppose the T[1] will include '*' if pattern has it in the beginning?
@@kitther It would be harder to initialize T. i.e String:adc pattern: *a*c, When it comes to T[0][1], that's when you considering if a and *a is a match, you would want to refer to T[0-1][1] or T[0][1-1] according to the algorithm provided. Obviously referring to T[-1][1] would result in intdexOutOfBoundary exception. So you need to consider T[0][1] alone and initialize it and it would be harder. The initialization with empty char in the beginning would be a lot easier, you just have to make '*' match empty char that'll work.
T[0][0] indicates when both the string and the pattern are empty. Which should return True
string -> abc & pattern -> a .. as per the logic, won't it return false ?
my mistake. It was clearly said in the beginning that, it is not a partial match rather complete one
Can you also explain the intuition behind why the formula for * and ? cases have come??
02:05 - exact reason behind the code
@@anvesh687 thanks
Tushar excellent recursive relation
please include recursive relation in every DP soln. as it gives insight to the problem very quickly.
Thanks!!
Shouldn't the condition in the code be "str[i] == pattern[j]" ?
Nevermind. figured it out.
I know that it is simpler to implement (this method), but it is way harder to understand than a Finite State Machine solution.
like your videos simple and effective..
He looks like Gautam Gambir. Agree?
You are god send Tushar
GOOD EXPLANATION AND THE BEST VIDEO ON UA-cam ABOUT THE REGULAR EXPRESSION MATCHING. tHANKS VERY MUCH
t should be T
no one talks about how the expression comes out first who needs people filling tables, show us how to get the idea for the expression
shouldn't T[1][2] be TRUE since we can replace the '?' with an empty string ""?
Roy teaching pattern matching while wearing v clashing patterns
You mean teaching patterns matching while wearing anti pattern dress ?
thanks!
Thank you!
why do you need to compress the multiple "*" into a single "*"?
Every * represent 0 or more characters, So if you put ***** or * it will be same.
gracias por este video amigo :)
I think the condition for "*" is not correct. At 8:07, T[2][4] should be True as "xa" matches with "x?y*".
how does xa match with x?y* ?
@@addiegupta '?' can be replaced with any character. Let's say we replace it with 'a'. And '*' means zero or more repetition of previous character. Let's take zero repetition of 'y'. That leaves is with 'xa'.
why do you remove the chars to match ? @ 6:09 ?
because one * would mean 0 or more characters and 3 * or 10 * or a million * one after other would also mean the same ..
shouldnt "b" be true for a*b regex? i think it should be true as we can have 0 or more occurrence of a.
Alright.Thanks.
+Tushar Roy Thanks for the great video! For regex, the algorithm will remain same apart from some conditions (example - for regex a* - while matching the patter I need to go back 2 columns and check if condition True is possible or not), right?
awesome
if (writeIndex > 0 && pattern[0] == '*')
temp[0][1] = true;
}
+Tushar Roy please clerify : why we are not taking pattern[1]== '*' instead of looking for index 0. As index 0 is always a empty.
Means index 0 always represent a empty character. So patter[0] contains null. So why we are checking patter[0]=='*'. Shouldn't we instead check pattern[1] == '*'
please check at 5.08
Hello, Anshu, I have the same doubt, did you find any explanation or solution further?. Reply me at Harshal Deolekar
failed to test "adceb", "*a*b"