Regular Expression Matching - Dynamic Programming Top-Down Memoization - Leetcode 10

[@NeetCode]

Dynamic Programming Playlist: kzbin.info/www/bejne/bWTVZH6Nnqqpr80

[@sudheerk7989]

I can't thank enough for this video! Even after spending nearly 3 hours on various videos showing direct DP (bottom-up) solution, and countless posts in Discuss section with no clear explanation, I could not understand how the formulae are derived. But.... this is gem of a video and probably the only video on KZbin explaining the Top-Down approach. In fact, it is better to try Top-Down approach in interviews. Directly trying to attack a problem with DP formula can lead to disasters. If the interviewer is not dumb expecting a specific answer involving DP, he/she/they should be okay with Top-Down+Memoization approach. Thanks again! Keep making such amazing videos.

[@jimwu3856]

To be honest, I never would have even guessed that this is a Dynamic Programming problem. Once you started explaining the decision tree, it ALL made sense. Thanks for teaching me something new!

[@TheRetrobek]

If someone didn't get the cache part, try printing out the (i, j) pairs with the following example: text="aaabaaa" and pattern = "a*b*a*". If you take a careful look, since we are backtracking, there are cases where we check the same (i, j) pairs. And that's why caching helps.

[@adityaathota501]

Ty so much, I was stuck trying to figure out where it was saving time

[@80kg]

thank you for pointing out the test case it's important for understanding why caching is effective at saving time

[@shalsteven]

how did you come with that example to identify the sub-problem?

[@sammykapoor8589]

Thanks this is very helpful

[@parambole8671]

If I crack my FB interviews it's only going to be because of this channel. Keep up the "NEET" work :)

[@NeetCode]

Good luck, you're going to do great!

[@Avinash_kumar_IITD]

same for me, I cracked Microsoft India interview

[@_ipsissimus_]

Hey boss, what coding problem did they ask you?

[@yukselpolatakbyk8468]

how did it go??

[@RaghavSharma-nt3hr]

did u crack?? 😅

[@auto8ot644]

Great explanation! I really like how you easily added memoization to the brute force algorithm. Other DP solutions were SO complicated. This explanation was perfect.

[@abhimanyuambastha2595]

Maybe its just me but I found the drawing explanation very confusing although the code made more sense. Usually I love all of Neetcode’s explanations but the pointer usage threw me off around first. There’s a similar problem Wildcard Matching and I solved it by checking the current j index and not j+1, thats why the j+2 was confusing. But in the end the code is very similar. I recommend others to try the Wildcard Matching problem its Leetcode 40 or 41

[@santoshr4212]

Thanks alot for helping me understand the issue, I was doing the bottom up and solution was failing in leetcode on last 2 test cases. After watching this video I understood we need to do bound check on index "i" - stupid of me missing such a basic thing. Now solution worked

[@chaoluncai4300]

2 more observations/ optimized caches: 1. If j+1 is * and both of its dfs() returned false, we actually dont need to re-check the matching condition again since j+1 is a *, means dfs(i+1, j+1) will fo sho return false due to s[i+1] != p[j+1] which is a *. That being said, we can change the last if (match) condition to else if condition~ 2. current cache will only does its job while next state's dfs() returned false (any next state is true indicates a solution is found). By storing only false returned val into cache will reduce memory space Both opts are negligible / pretty insignificant since either of them only saved limited constant time/space

[@chinmaym92]

I really appreciate how clean your code was and was so easy to understand

[@shai1esh]

if this is the case below then : '*' Matches any sequence of characters (including the empty sequence). def isMatch(self, s: str, p: str) -> bool: # top down memo cache = {} def dfs(i, j): if(i, j) in cache: return cache[(i, j)] if i >= len(s) and j >= len(p): return True if j >= len(p): return False if p[j] == '*': # Check if the '*' matches an empty sequence or matches one or more characters cache[(i, j)] = dfs(i, j + 1) or (i < len(s) and dfs(i + 1, j)) return cache[(i, j)] match = i < len(s) and (s[i] == p[j] or p[j] == "?") if match: cache[(i, j)] = dfs(i + 1, j + 1) return cache[(i, j)] cache[(i, j)] = False return False return dfs(0, 0)

[@emretekmen1602]

you need to explain how the cache actually saves time. How does storing the indexes along with a bool value save any time?

[@袁丽君-s7c]

This explanation makes the whole process clean and simple.

[@dollyvishwakarma2]

OMG, the question looked so tough, but you made it soo easy !! Another awesome explanation. Great fan of your NEET coding style :)

[@manivannansivaraj7324]

Loved your solution, Neet. I was breaking my head to get it working. Thanks for the neat explanation and a great walkthrough :)

[@pranavkashyap8610]

The dramatic decrease in time taken to execute after using cache surprised me . Thanks for the explanation and code

[@VishalKumar-kr9me]

How easy you make a hard problem is unbelievable !!!!!! Salute to you

[@jacques-dev]

For anyone getting confused with the solution to this problem, I found the bottom-up approach to be much more intuitive. Just my experience, I know everyone is different.

[@replicadse]

I'd always tend to avoid using "i" and "j" because they look very similar in most fonts. Use "i" and "k" to improve readability -> remember: code is read heavy.

[@eyosiasbitsu4919]

I'll have my google interview in October and this channel is really helping me in my preparation. if i pass then i'll be your biggest supporter neet!

[@orogheneemudainohwo3493]

How do you have an October interview scheduled in May? Full time or internship? Goodluck

[@nealp9084]

did you pass?

[@arpanbanejee5143]

Simply mind-blowing explanation, you made it so simple!! Thanks you! Please keep up the good work!

[@hakoHiyo271]

Great explanation! You explained the algorithm very clearly. I'm not even Python guy, but I still liked your video!

[@kocot.]

Instead of optimizing it with cache, I've got an almost identical result (1300ms->50ms) by simply ensuring you don't process subsequent stars. So if there is a*a*a*, you'd only check it once. Now the cache seems obvious, but that addressed directly the most compute intensive cases :) Funny to see how it's same efficient. Using both would probably improve it even further.

[@michaeldunlap2693]

This is a fabulous and thorough explanation. The decision tree explanation and visual for the asterisk was what did it for me. Thank you!

[@Varukimm]

I struggled with this problem today without PD. In your example a = a*b* should give true because we use a and a* and remain with 0 b. Correct would be a = a*b

[@xinchenyi9878]

The clearest explanation I've seen!!! You are awesome :)

[@buttercup5029]

I was struggling a lot with this question. Your video cleared my doubts. Thanks for sharing!

[@diveshkubal2936]

A correction: if j>=len(p): return i >= len(s) # If pattern is exhausted, return True only if string is also exhausted

[@sauravchandra10]

You make hard problems very easy. Thanks for explaining.

[@vdyb745]

What a brilliant solution and in-depth explanation for this seriously hard problem !!! WOW .... Thank you !!!!

[@木漏れ日-v9n]

The base case can be simplified with if j == n: return i == m

[@thinja]

Wow so much easier to understand than the DP solution! Thanks for showing your mistakes as well

[@yangyue2791]

Yeah, that problem is so hard. I tried to use loops to compare character by character, and deal with * differently. Though, that way did not work well.

[@tanaysingh5348]

the question description feels really incomplete without your explanation , thanks a lot

[@zl7460]

Thank you for the explanation. I thought according to the problem statement, 'c*' cannot be empty, which was very misleading by Leetcode.

[@kanwarkajla]

great explanation .....also the vibe of ur videos is relaxing!

[@meto4545]

I have a question, why the testcase - s="a", p=".*..a*" has to return false? I mean we just make ".*.." a 0 character string "" and the rest we make one "a". Edit: Nevermind I thought '.' can be a 0 character string since in the question it doesn't say anything about it.

[@Whatthetrash]

Thank you so much for this. After weeks (!) of trying to solve this problem on my own, I decided to look it up and lo and behold -- the solution involves a bunch of stuff that I have never heard of. I feel a bit better (and I need to learn about Dynamic Programming now). >_< Thanks again for the elegant, succinct solution.

[@rahuljain281]

What an explanation sir ji❤. After this, I was able to solve wildcard matching by myself.

[@somilsinghai5966]

This question makes me appreciate the hard work of people who have created the full-blown regex.

[@Iamnoone56]

Thanks Hokage for explaining it really well.Seen a lot of videos where people directly start drawing table.Will memoized soln be enough for an interview or do we have to give a bottom up soln too??

[@iharshgarg]

i checked so many videos of this problem.. but there's simply no compedition to you bro. keep the neet work up bro/>

[@thepoonhound3003]

you forgot to emphasize during the drawing segment that the reason why it was ok for string p to not match string s, where s = aab and p = c*a*b was becuz the asterik allows c to occur 0 times, its not like what counts as true is if all of the characters in string s are able to be accounted for by stuff in string p, while strickly going left to right through the strings and never backtracking

[@jerryjohnthomas4908]

can some one explain what happens if i==m and j

[@lootlook5148]

WTF !! Bro You made clear in just 20 minutes🤩

[@yukselpolatakbyk8468]

You make this question easy to udnerstand. Thank you for all your amazing solutions!!

[@for_whom_the_bell_tolls]

Wow man your explanation is just fantastic!

[@z08840]

by switching "use" and "don't use" in or return statement you can significantly cut complexity down even without memoization

[@pranavsharma7479]

thnks bro i was not getting how to solve this , this is same as wildcard matching with a twist

[@akhma102]

Thank you, Neet! Great Explanation!

[@paneercheeseparatha]

Thanks. its a pretty difficult problem.

[@AbanoubAsaad-YT]

BEST EXPLANATIONS ARE HERE :) Thank you so much for these quality videos!

[@Chirayu19]

I think the time complexity would be O(N^2M) and not O(N*M) since we have to iterate through the s in case of "*". Please do correct me if I am wrong. Thanks!

[@python-developer521]

leet code accepting if 6th line change to j>len(p) instead of j>=len(p)

[@notsadsisyphus6224]

i seriously love your video i swear you dont waste time i love it

[@comander47]

this problem took me soo much time to understand, thank you dude

[@saadkhan4049]

You made it look so simple. Thank you!

[@capriworld]

Best explanation ever found for this problem.

[@jonathanandres1657]

Great explanation! :) @NeetCode what tool do you use to write and draw ? Any specific brand, I'm looking for this kind of tools

[@shashwatmaru9238]

Hey what would be the Time and Space complexity ? Backtracking with memoization means 2^n?

[@juliramoos]

Perfect explanation! Thank you. And the code looks good.

[@mrpotatohasabanana]

Does this code cover TC where pattern ends with .* , like s="aab" p="aaa*.*" Iam getting false for such .* Ending cases where I need to ommit * but code returns false as we have passed s length

[@sauravchandra10]

If there is one thing which I am not sure is how will the subproblems repeat. If anyone has any intuitive way, pls let me know.

[@biancafuu]

Does anyone know why does the solution run into max recursion depth problem if I set the condition as : (dfs(i+1, j) and match) or dfs(i, j+2) for the dfs call instead of : dfs(i, j+2) or ((dfs(i+1, j) and match)) (I switch the order of the recursion call) 🤔

[@nikosreg9710]

I think it's because you don't allow short-circuiting evaluation of your logical expressions to take place, saving you from the fact that there will always be one branch in your decision tree that accepts the star (left branch in the diagram in the video), thus leading to an infinite branch. Note: the fact that one branch of the tree can be infinitely extended is not false. That's the notion of "*" anyways. You just should make use of python's short-circuiting to avoid this infinite trap...

[@kaartiknagarajan5009]

I've recoded your solution and it's brilliant. However, I've been trying to follow the stack trace of the program execution to convince myself when the first if statement would execute "if (i, j) in cache: return cache([i, j])". I know it does because I tried removing it and got a TLE error o Leetcode, but I don't see when it would be needed as we always progress into a deeper DFS and cache. Would appreciate an explanation if you could please! Thank you.

[@yangyue2791]

Would you like to explain the case like "s=aab p=a*ab"? In case like that, we need to take care how much times * copies its preceding letter.

[@nikosreg9710]

I still don't get how cache helps us... Where is the backtrack step that would benefit from the use of a cache? Don't we use the indices' pair (i, j) only once and then move to the next character?🤔

[@xyhan98]

Hi NeetCode, not sure if LeetCode has added some new test cases, but seems like both top down and bottom up approaches are experiencing TLE for test case s = "aaaaaaaaaaaaaaaaaaab", p = "a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*". Other than that, thanks for your great explanation!

[@eldercampanhabaltaza]

+1

[@ruizhu5295]

I really appreciate your explanation, so clean, so logical!

[@MonkeyHitsDonkey]

Can someone please explain how the time complexity is improved from O(2^n) to O(m*n) using a cache

[@Terracraft321]

"Bilguun If someone didn't get the cache part, try printing out the (i, j) pairs with the following example: text="aaabaaa" and pattern = "a*b*a*". If you take a careful look, since we are backtracking, there are cases where we check the same (i, j) pairs. And that's why caching helps."

[@letscode1000]

Could anyone explain how the cache works, I understand the top-down, but don't understand memo as you said, it works well as memo, but when I trace the recursion, cannot see how the cache works?

[@TheRetrobek]

Since we are backtracking, our explorations have a chance of repeating the same (i, j). Try printing out the (i, j) pairs with example as: text="cccbccc" and pattern = "c*b*c*"

[@davidm3614]

Great video! During your explanation of the examples I had one question, why does "a.." != "aa" if the character "." can represent zero or more of any character? I was thinking that the first period could be "a" and the second period can be empty therefore making aa = aa. Did I understand incorrectly?

[@jimmyliu3101]

Periods must represent a character, they can't be an empty string, only the star can be an empty string.

[@Demo-yc8fb]

what if s reaches the end but p does not? That will not always return a true right? Where did we cover that case?

[@chizhang9135]

solve in one line return bool(re.fullmatch(p, s))

[@MutuallyBro]

Very good explanation, love the channel!

[@rjkal]

Wow! You made it look like a piece 'o cake. Thanks, I really appreciate it.

[@nagasivakrishna5660]

man love ur explanation ,great man ,no words love u man

[@JameS00989]

Super awesome explanation NeetCode 🎉Thanku

[@ArpitDhamija]

I tried your method. Did in C++, both recurssion and memoization but there was no big significant difference in the time. Gap was only 20ms. But there is huge time difference in your code. Hows that possible

[@ashkankipati]

Could you explain wildcard matching, a similar problem to this one?

[@MaxFung]

thank god for this guy i was STUCK

[@Tyokok]

Thanks for great explain! Do you also have an explain on complexity analysis of this recursive call? Thank you!

[@Team_sih]

but I got a doubt how are we looping the string if we ae not using any loop. like it will check all the conditions for 1 time but how is it looping ??? can anyone help?

[@nishapaila7870]

just a clean explanation amazing

[@sungiv]

this algorithm is not working for case s="aa" and p="*". since its checking for j+1 for * its not working..

[@Demandd]

Read the constraints - “it is guaranteed for each appearance of the character '*', there will be a previous valid character to match.” So you will never get an input containing a ‘*’ without a letter before it

[@mayureshgharat1600]

Excellent tutorial !!! In case of P[ j + 1] = '*', why don't we check dfs(i, j+2) only when there is no match. IOW, why don't we do this : if (!match) { dfs(i , j+2) } else { dfs(i + 1, j) } why do we have to do: dfs(i, j + 2) even in case of a match?

[@weiwang4045]

Because it can be faster... in that, Consider 'a*a*a*aaa' match 'aaa', if we check dfs(i, j+2) even in case of current position match 'a' == 'a', the pattern would quickly skip all 'a*' cases, match the string with the tailing 'aaa' pattern, and return True whatsoever result returned from the other 'matched' side, because of the shortcut feature of OR operator. And in fact, on the 'matched' side, because a* would devour all matched letter 'a' and goes to the very end of the string '' , only to find '' is not matched and return False. So if you don't check dfs(i, j+2) before matched side is finished with a False, the OR expression have to wait for the other dfs(i, j+2) side result to determine the final boolean value. True || (whatsoever) vs False || True, obviously the former is faster. Just my opinion.

[@80kg]

Aren't those two ways are same? and Wei Wang's explanation only can help with his example. In the case of "bc" "a*a*bc", it jump over to j + 2 because of not matched.

[@amitavamozumder73]

can i do it just by using a stack? push any pattern and if found star removes all stack top char and pop it and move on. in case of .* we just push it in the stack and move on..

[@sunginjung3854]

Thank you for the great video! Is there any chance you could also solve Minimum Difficulty of a Job Schedule (LC 1335)? I would really appreciate it.

[@prithulbahukhandi1714]

bro good work. Can you give me 1 example where you are making use of pair stored in the cache. I don't get it, how are sub-problems repeating?

[@AshishKumar-dk5ve]

"cccbccc" "c*b*c*" (i j) cached values used in below cases 1 4 2 4 3 4

[@prithulbahukhandi1714]

@@AshishKumar-dk5ve Thank you ashish got it!

[@akash6895]

Your solution may give incorrect answer for some examples for eg. If s='aabbddefgh' and p='.*efgh' . In this case your solution will return False. i.e string does not match the pattern because of bounding condition of i and j that you have applied.But in actually the string does matches the regular expression.

[@axay3.0]

this is called Codeagasm. Mind blowing.

[@aldogutierrez8240]

Very good explanation thanks!

[@NAVNEET549]

Awesome explanation. Thank you so much

[@scottchen2094]

Can someone explain why we dont add cache for line 11 & line 13 the two base cases?

[@daved1113]

Excellent work. Earned a sub. Keep it up.

[@sivaprakashkkumar9691]

Top down approach means you have to start from top(size-1) , you are mentioning all your vedios recursion top down approach but actually it is backtracking bottom up approach

[@sumeetchawla3545]

Amazing explanation .. Really thankful for your great efforts.. :)

[@NeetCode]

Glad it was helpful!

[@sameerkumar-uq2ic]

how did he changed the leetcode code editor to this color

[@KhoaNguyen-bu7ri]

I don’t know if it’s too much to ask but can you also provide solution in Java 😅. Really love your videos but just can’t keep up with Python. Thanks!

[@chongwen]

great explanation without sophisticate dp, can't thanks more!

[@thisissheraf2633]

Appreciate your explanation thank you