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

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Twitter: / neetcode1
Discord: / discord
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/regular-...
Code on Github: github.com/neetcode-gh/leetco...
0:00 - Read the problem
3:55 - Drawing Solution
19:00 - Coding Solution
leetcode 10
This question was identified as a google interview question from here: github.com/xizhengszhang/Leet...
#regular #expression #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@NeetCode]

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

[@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?? 😅

[@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!

[@dollyvishwakarma2]

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

[@chinmaym92]

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

[@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!

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

[@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!

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

[@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?

[@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!

[@vdyb745]

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

[@yukselpolatakbyk8468]

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

[@user-po5dk2xr7d]

This explanation makes the whole process clean and simple.

[@pranavkashyap8610]

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

[@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??

[@AbanoubAsaad-YT]

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

[@thinja]

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

[@kanwarkajla]

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

[@ruizhu5295]

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

[@VishalKumar-kr9me]

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

[@jerryjohnthomas4908]

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

[@sauravchandra10]

You make hard problems very easy. Thanks for explaining.

[@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?

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

[@Tyokok]

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

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

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

[@shashwatmaru9238]

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

[@saadkhan4049]

You made it look so simple. Thank you!

[@scottchen2094]

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

[@comander47]

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

[@juliramoos]

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

[@user-or7qq1bz1q]

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?

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

[@capriworld]

Best explanation ever found for this problem.

[@rahuljain281]

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

[@krugerbrent4270]

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

[@jonathanandres1657]

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

[@notsadsisyphus6224]

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

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

[@daved1113]

Excellent work. Earned a sub. Keep it up.

[@MutuallyBro]

Very good explanation, love the channel!

[@NAVNEET549]

Awesome explanation. Thank you so much

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

[@nishapaila7870]

just a clean explanation amazing

[@iharshgarg]

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

[@ashkankipati]

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

[@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?

[@anonofDeath]

Can someone explain to me how the aab == c*a*b? Isn't it suppose to cover the entire string?

[@lootlook5148]

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

[@Avuvos]

Great video and explanation thank you!

[@z08840]

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

[@sachin_yt]

I loved it man, thanks a lot :)

[@nagasivakrishna5660]

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

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

[@pranavsharma7479]

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

[@xinniu3145]

Thank you! this is owesome!

[@emretekmen1602]

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

[@somilsinghai5966]

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

[@aldogutierrez8240]

Very good explanation thanks!

[@sungiv]

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

[@JameS00989]

Super awesome explanation NeetCode 🎉Thanku

[@taroserigano6546]

Super thanks for this!

[@emmatime2016]

Great video!!!! Thank you!

[@purnimadas768]

Thank you for the very good video

[@thisissheraf2633]

Appreciate your explanation thank you

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

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

[@sameerkumar-uq2ic]

how did he changed the leetcode code editor to this color

[@anujdoshi882]

Amazing explanation!

[@yongquanrao7398]

Great one. Thanks.

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

[@haodantan2014]

Best explanations! Thank you!

[@NeetCode]

Thanks 😊

[@tanaysingh5348]

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

[@MsSkip60]

Awesome mate!

[@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!

[@zl7460]

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

[@siddharthpandey8516]

This was perfect!

[@MaxFung]

thank god for this guy i was STUCK

[@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)

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

[@dineshkannam8078]

You are a legend.

[@tanayshah275]

great explanation!

[@mirshodoripov1035]

can you solve it using only re module in python?

[@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*"

[@sumeetchawla3545]

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

[@NeetCode]

Glad it was helpful!

[@danielsun1993]

The best explanation!!!

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

[@lingyunsu1589]

Best explanation ever!

[@saikat511]

will it work with s: aaa, p: aab*a*c*a ??

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

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

[@pinkylover911]

you are talented

[@pulakammalathy6968]

Thank you so much

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

[@koppan]

Thanks a lot :)