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
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.
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?
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:)
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 ( ruclips.net/video/3ZDZ-N0EPV0/видео.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.
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.
@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.
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
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?
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]; } }
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 :)
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
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.
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?
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!
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 ?
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.
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
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?
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 ?
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)
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?
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
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?
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?
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.
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
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.
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
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.
@@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'.
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.
+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?
leetcode's similar problem 44. Wildcard Matching, C++ code for the approach explain above : class Solution { // remove multiple * 's E.g : pc*** to pc* string remove (string p){ bool first = true ; int j=0; for(int i=0;i
![Burst Balloon Dynamic Programming[Leetcode]](http://i.ytimg.com/vi/IFNibRVgFBo/mqdefault.jpg)
Thanks to all Indian guys on RUclips, I'm a well-paid software engineer!
yo wtf have u posted in yur channel man like wtf?????
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
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
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.
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.
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:)
7 years OLD still GOLD
Wow! Explanation was super simple and clear. Thank you so much tushar****
Thanks for the videos, please keep making them. Will recommend to all my friends~
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 ( ruclips.net/video/3ZDZ-N0EPV0/видео.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.
Brilliant explaination sir❤
This video is crucial for dynamic programing tabulation approach - Thank you Tushar
tushar sir u r making our path easier
As usual excellent work Tushar! You rock man! Keep continuing the good work buddy!
Thanks a lot. I understand when i see the picture.
For case 2:
Matching the pattern this way might help in understanding --
b a *
b a
or
b a *
b a
Can be further optimised by using boolean T[][]=new boolean[string.length+1][writeIndex+1]; and changing (int j=1;j
Very easy way of explanation , thanks.
BEST WILDCARD MATCHING EXPLANATION EVER.
Excellent explanation
Your videos help me a lot! I just want to say thank you!
All your videos are awesome.. You are the best teacher.
Great explanation. Thank you.
Clear and concise explanation!
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.
Thank you so much for a such great explanation
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
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
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?
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];
}
}
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.
GOOD EXPLANATION AND THE BEST VIDEO ON RUclips ABOUT THE REGULAR EXPRESSION MATCHING. tHANKS VERY MUCH
t should be T
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: ruclips.net/video/l3hda49XcDE/видео.html
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
Good Explanation Tushar!!
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.
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.
Tushar excellent recursive relation
please include recursive relation in every DP soln. as it gives insight to the problem very quickly.
Thanks!!
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?
What an awesome explanation!
I know that it is simpler to implement (this method), but it is way harder to understand than a Finite State Machine solution.
Great explanation! Thanks for the help!
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!
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 ?
Roy teaching pattern matching while wearing v clashing patterns
You mean teaching patterns matching while wearing anti pattern dress ?
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.
Wow, excellent explanation!
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
You are god send Tushar
I'm here because CoPilot suggested this video in an auto-completed comment. (yes really)
Thank you it would help a lot to me
like your videos simple and effective..
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?
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
Amazing thank you
He looks like Gautam Gambir. Agree?
If the "*" is at the start of the pattern taking it from left or above should fail.
I love you man! :D I wish I could get you a beer
He doesn't drink
11:27 - Very important part on the video
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 ?
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 ?
ruclips.net/video/EOWHWVd540U/видео.html
gracias por este video amigo :)
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)
Great work 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?
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
why is their difference in regex and wildcard solution for pattern[i-1] = '*' for 0 occurance of character before '*'?
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
Can you also explain the intuition behind why the formula for * and ? cases have come??
02:05 - exact reason behind the code
@@anvesh687 thanks
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
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?
I am unable to understand when there is * mark what to do?
Why null string is not matched withs star in row 1
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.
Can we extend this logic to contain a delimiter character say '/' whose first instance does not map to '*' of any character ?
Doesn't '?' mean that a is optional rather than "any 1 character between a and b"
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
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
Thank you!
is this the same as the regular expression matching dp problem?
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
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.
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
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'.
thanks!
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.
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 ""?
awesome
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.
Tushar Roy and Adul Bari
How did you derived the formula at 2:04 ?
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?
Shouldn't the condition in the code be "str[i] == pattern[j]" ?
Nevermind. figured it out.
leetcode's similar problem 44. Wildcard Matching,
C++ code for the approach explain above :
class Solution {
// remove multiple * 's E.g : pc*** to pc*
string remove (string p){
bool first = true ;
int j=0;
for(int i=0;i
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.