Wildcard Matching Dynamic Programming

/ tusharroy25
github.com/mis...
github.com/mis...
/ tusharroy25
Implement wildcard pattern matching with support for '?' and '*'

[@MasterSergius]

Thanks to all Indian guys on KZbin, I'm a well-paid software engineer!

[@rajeevsingh5453]

yo wtf have u posted in yur channel man like wtf?????

[@rupesh_dharme]

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.

[@dominic_lee]

thank you so much for this comment

[@abhishekrbb9111]

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

[@kitty_tax]

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];

[@rahulagrawal3611]

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?

[@codewithsunny981]

He mistakenly removed the '*' character but explained correctly....comparison should be in x?y* and xa.

[@dileepmeena8749]

can we match empty string ( ' ' ) with * ( because * also match 0th string)..??

[@miracledoh4020]

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]; } }

[@dera_ng]

Wow... There is a sort of beauty in dynamic programming.

[@securelyinsaycure]

The only video I have watched so many times at different stages of my career(*pure gold*).

[@polavenki]

10:44 - we shouldn't wipe "*" in the explanation part?

[@vasanthykolluri]

totally agree...this is most trickiest part of the algo. @Tushar: Pls add that explanation if possible.Thanks in advance.

[@dy0953]

@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.

[@sudheerkumar4130]

Correct , thank god you raised this concern

[@nathann4291]

@@dy0953 what does "since top already match the current char" mean?

[@ankuragarwal4014]

@@dy0953 what does "since top already match the current char" mean? please tell about it

[@aviadshiber6232]

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?

[@kanikaverma6409]

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 ?

[@kamalsmusic]

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?

[@guangyang5116]

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.

[@sauravagrawal5013]

Can be further optimised by using boolean T[][]=new boolean[string.length+1][writeIndex+1]; and changing (int j=1;j

[@ialpha6431]

For case 2: Matching the pattern this way might help in understanding -- b a * b a or b a * b a

[@neelesh2023]

your energy level is on another level

[@siddharthkalani7535]

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?

[@nikhilbhardwaj6055]

sir if there is * in pattern then we should check left, upside and 'DIAGONALLY' also otherwise some test cases will be failed

[@vivek5562]

I was also thinking about same. if you match * with "a" then this will fail.

[@sameerranjan2039]

@@vivek5562 * and "a" should match and if u follow this algorithm it does match. It doesn't fail.

[@rahulagrawal3611]

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?

[@ymnik100]

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 ( kzbin.info/www/bejne/aYuni2CEZaqDjJI ) 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.

[@apexstate3127]

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 ?

[@CodingWithPrakash_]

kzbin.info/www/bejne/e4C6eYqMmZpnZrc

[@ewibowo74]

I don't understand about his explanation at 5:02 that * match empty string. However, he wrote F for matrix 0 and *.

[@kishores5121]

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!

[@SWE_69]

7 years OLD still GOLD

[@AbhishekKumar-oj4zm]

tushar sir u r making our path easier

[@ShaliniNegi24]

I am unable to understand when there is * mark what to do?

[@techbarikcom]

Wow! Explanation was super simple and clear. Thank you so much tushar****

[@sahilsoni6090]

Is it necessary to convert multiple stars into one or can we keep them as it is ?

[@jdragon8184]

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

[@chiragkhubdikar900]

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?

[@dominic_lee]

? can only be one character. x*y would match this though

[@jellydg988]

Thanks for the videos, please keep making them. Will recommend to all my friends~

[@SAHILOMATIC180]

why is their difference in regex and wildcard solution for pattern[i-1] = '*' for 0 occurance of character before '*'?

[@venkatesanr89]

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 ?

[@nehaagrawal5457]

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?

[@cantwaittowatch]

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

[@asiskumarroy4470]

is this the same as the regular expression matching dp problem?

[@Shabnam_Bandyopadhyay]

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 .

[@404TimeOut]

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.

[@vamsi54krishna]

false is expected answer as string "ac" doesn't have 'b' char which is required by pattern.

[@kkk7410]

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.

[@kkk7410]

+kk k Also ,if this has to work for right to left,the pattern should be symmetrical ?

[@kkk7410]

+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 ?

[@kkk7410]

+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.

[@sukanyapai8984]

Can you also explain the intuition behind why the formula for * and ? cases have come??

[@anvesh687]

02:05 - exact reason behind the code

[@sukanyapai8984]

@@anvesh687 thanks

[@anishsuman1371]

Why null string is not matched withs star in row 1

[@piyushsharma1638]

Very easy way of explanation , thanks.

[@summermoonspace]

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:)

[@queueoverflow]

Thanks a lot. I understand when i see the picture.

[@ivandrofly]

This video is crucial for dynamic programing tabulation approach - Thank you Tushar

[@winsterjose2574]

string -> abc & pattern -> a .. as per the logic, won't it return false ?

[@winsterjose2574]

my mistake. It was clearly said in the beginning that, it is not a partial match rather complete one

[@maneshwarsingh8688]

shouldn't T[1][2] be TRUE since we can replace the '?' with an empty string ""?

[@srikantadatta8695]

As usual excellent work Tushar! You rock man! Keep continuing the good work buddy!

[@ssjohnsmith3]

If the "*" is at the start of the pattern taking it from left or above should fail.

[@silent_watchmen]

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?

[@silent_watchmen]

+Tushar Roy Thanks for reply and appreciate if you could take a look. Thanks. tinyurl.com/hrh8qj3

[@crystal101-77]

Brilliant explaination sir❤

[@soumavomondal2705]

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 :)

[@vitaliistoian]

It's explained here: kzbin.info/www/bejne/omTLlZRqbr2Weqc

[@arna591]

BEST WILDCARD MATCHING EXPLANATION EVER.

[@balajiarumugam1876]

what is difference between regular exp match and wildcard match?? pls explain me.

[@anandtiwari1541]

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

[@benjaminrogge4959]

Thanks for the great video! Is it correct that this algorithm won't work, if you have wildcards in the front of your pattern?

[@benjaminrogge4959]

+Tushar Roy you are right. My initial implementation was wrong

[@kitther]

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.

[@wensun510]

It will deal with situation when * represent empty string in the beginning. i.e s:abcd p:*abcd

[@kitther]

@@wensun510 I suppose the T[1] will include '*' if pattern has it in the beginning?

[@wensun510]

@@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.

[@gulshanjangid3470]

T[0][0] indicates when both the string and the pattern are empty. Which should return True

[@anilduttyemmanuru6359]

Great explanation. Thank you.

[@ryanben3988]

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.

[@prat534]

Can we extend this logic to contain a delimiter character say '/' whose first instance does not map to '*' of any character ?

[@tomma1268]

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.

[@vipulmishra8682]

Clear and concise explanation!

[@anonymoussloth6687]

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

[@TL-fe9si]

Your videos help me a lot! I just want to say thank you!

[@s1337m]

What if a partial match was ok? how would the DP formula change?

[@sharma-raju]

Thank you so much for a such great explanation

[@harishgovindan]

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)

[@anshusharma11]

All your videos are awesome.. You are the best teacher.

[@vanihemmige]

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?

[@DheerajKumarBarnwal]

First try to understand what T[i][j] represent, then you will get your answer

[@pranayreddy6337]

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?

[@ankitgomkale11]

I think the condition for "*" is not correct. At 8:07, T[2][4] should be True as "xa" matches with "x?y*".

[@addiegupta]

how does xa match with x?y* ?

[@ankitgomkale11]

@@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'.

[@himanshijain7585]

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

[@amanpreetsinghbawa1600]

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

[@nlharish]

Shouldn't the condition in the code be "str[i] == pattern[j]" ?

[@nlharish]

Nevermind. figured it out.

[@abhishes]

Doesn't '?' mean that a is optional rather than "any 1 character between a and b"

[@xiaofeiguo2091]

why do you need to compress the multiple "*" into a single "*"?

[@rajeshbajya6520]

Every * represent 0 or more characters, So if you put ***** or * it will be same.

[@bantyK]

How did you derived the formula at 2:04 ?

[@atouba-0]

Excellent explanation

[@curiosull]

I know that it is simpler to implement (this method), but it is way harder to understand than a Finite State Machine solution.

[@amanpreetsinghbawa1600]

Tushar excellent recursive relation please include recursive relation in every DP soln. as it gives insight to the problem very quickly. Thanks!!

[@anshusharma11]

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.

[@anshusharma11]

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

[@30harshal]

Hello, Anshu, I have the same doubt, did you find any explanation or solution further?. Reply me at Harshal Deolekar

[@kamalsmusic]

Also how do you do it with 1D array?

[@Arunk054]

Yes it is possible with just O(pattern) space complexity. See my solution here: gist.github.com/arunk054/f78091bf5e44ce5386a8035408a08377

[@Arunk054]

Btw.. Nice meeting you again @Kamal. Remember Microsoft 2016?

[@vsg321]

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.

[@kshitijjain8544]

What an awesome explanation!

[@Null_pointer_exceptn]

shouldnt "b" be true for a*b regex? i think it should be true as we can have 0 or more occurrence of a.

[@Null_pointer_exceptn]

Alright.Thanks.

[@kitty_tax]

+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?

[@DhruvPatel-kg5ut]

Why t[0][4] is false?

[@shayanmalinda7409]

It should be true no?

[@vitaliistoian]

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.

[@siddharthagarwal8662]

Good Explanation Tushar!!

[@nagarjuna119]

why do you remove the chars to match ? @ 6:09 ?

[@itsmewaqar]

because one * would mean 0 or more characters and 3 * or 10 * or a million * one after other would also mean the same ..

[@jinliu5928]

Great explanation! Thanks for the help!

[@cskcsk6370]

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.

[@mohitgautam6365]

Thank you it would help a lot to me

[@shobhitchaturvediindia]

like your videos simple and effective..

[@xw7628]

Roy teaching pattern matching while wearing v clashing patterns

[@shariqueshahab]

You mean teaching patterns matching while wearing anti pattern dress ?

[@user-re6yu6xk6d]

Wow, excellent explanation!

[@shubhrojyotikabiraj8322]

For pattern: ****a****b**c and str: dsfsabc your logic is not working. It should give true but all the cells(except first cell) are false therefore ans is ultimately false.

[@timbabb2508]

I'm here because CoPilot suggested this video in an auto-completed comment. (yes really)

[@metaalphabrawlstars7697]

GOOD EXPLANATION AND THE BEST VIDEO ON KZbin ABOUT THE REGULAR EXPRESSION MATCHING. tHANKS VERY MUCH

[@nathann4291]

t should be T

[@Official-tk3nc]

He looks like Gautam Gambir. Agree?

[@daniyaryeralin9813]

I love you man! :D I wish I could get you a beer

[@Ayoub-adventures]

He doesn't drink

[@dush]

You are god send Tushar

[@ivandrofly]

11:27 - Very important part on the video

[@VanjeAv]

Amazing thank you

[@mariochavez3546]

gracias por este video amigo :)

[@maharajak6578]

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

[@muzgash97]

Great work thank you!

[@rashmikiranpandit8962]

Thank you!

[@darshanbari2439]

Tushar Roy and Adul Bari

[@hyunjeongcho4037]

thanks!