Regular Expression Matching - Dynamic Programming Top-Down Memoization - Leetcode 10
Вставка
- Опубліковано 25 чер 2024
- 🚀 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. - Наука та технологія
Dynamic Programming Playlist: ua-cam.com/video/73r3KWiEvyk/v-deo.html
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 UA-cam 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.
If I crack my FB interviews it's only going to be because of this channel. Keep up the "NEET" work :)
Good luck, you're going to do great!
same for me, I cracked Microsoft India interview
Hey boss, what coding problem did they ask you?
how did it go??
did u crack??
😅
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!
I really appreciate how clean your code was and was so easy to understand
OMG, the question looked so tough, but you made it soo easy !! Another awesome explanation. Great fan of your NEET coding style :)
The clearest explanation I've seen!!! You are awesome :)
This is a fabulous and thorough explanation. The decision tree explanation and visual for the asterisk was what did it for me. Thank you!
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.
Ty so much, I was stuck trying to figure out where it was saving time
thank you for pointing out the test case it's important for understanding why caching is effective at saving time
how did you come with that example to identify the sub-problem?
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.
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
Simply mind-blowing explanation, you made it so simple!! Thanks you! Please keep up the good work!
BEST EXPLANATIONS ARE HERE :)
Thank you so much for these quality videos!
I was struggling a lot with this question. Your video cleared my doubts. Thanks for sharing!
Great explanation! You explained the algorithm very clearly. I'm not even Python guy, but I still liked your video!
I really appreciate your explanation, so clean, so logical!
This explanation makes the whole process clean and simple.
What a brilliant solution and in-depth explanation for this seriously hard problem !!! WOW .... Thank you !!!!
You make this question easy to udnerstand. Thank you for all your amazing solutions!!
great explanation .....also the vibe of ur videos is relaxing!
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
Best explanation ever found for this problem.
You made it look so simple. Thank you!
i seriously love your video i swear you dont waste time i love it
The dramatic decrease in time taken to execute after using cache surprised me .
Thanks for the explanation and code
Excellent work. Earned a sub. Keep it up.
You make hard problems very easy. Thanks for explaining.
Wow so much easier to understand than the DP solution! Thanks for showing your mistakes as well
this problem took me soo much time to understand, thank you dude
Very good explanation, love the channel!
Awesome explanation. Thank you so much
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??
How easy you make a hard problem is unbelievable !!!!!! Salute to you
Perfect explanation! Thank you. And the code looks good.
Wow! You made it look like a piece 'o cake. Thanks, I really appreciate it.
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.
man love ur explanation ,great man ,no words love u man
Great video and explanation thank you!
I loved it man, thanks a lot :)
Thank you! this is owesome!
WTF !! Bro
You made clear in just 20 minutes🤩
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!
How do you have an October interview scheduled in May? Full time or internship? Goodluck
did you pass?
Super awesome explanation NeetCode 🎉Thanku
Very good explanation thanks!
You are a legend.
Best explanations! Thank you!
Thanks 😊
Awesome mate!
Super thanks for this!
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
Great video!!!! Thank you!
Appreciate your explanation thank you
Amazing explanation!
This was perfect!
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.
The best explanation!!!
by switching "use" and "don't use" in or return statement you can significantly cut complexity down even without memoization
Great one. Thanks.
Thanks for great explain! Do you also have an explain on complexity analysis of this recursive call? Thank you!
Thank you for the very good video
Best explanation ever!
What an explanation sir ji❤. After this, I was able to solve wildcard matching by myself.
thnks bro i was not getting how to solve this , this is same as wildcard matching with a twist
great explanation!
thank god for this guy i was STUCK
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.
This question makes me appreciate the hard work of people who have created the full-blown regex.
Great explanation! :) @NeetCode what tool do you use to write and draw ?
Any specific brand, I'm looking for this kind of tools
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.
you are talented
Amazing explanation .. Really thankful for your great efforts.. :)
Glad it was helpful!
you need to explain how the cache actually saves time. How does storing the indexes along with a bool value save any time?
i checked so many videos of this problem.. but there's simply no compedition to you bro. keep the neet work up bro/>
Thank you so much
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)
Thanks a lot :)
Hey what would be the Time and Space complexity ? Backtracking with memoization means 2^n?
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.
Thank you for the explanation. I thought according to the problem statement, 'c*' cannot be empty, which was very misleading by Leetcode.
the question description feels really incomplete without your explanation , thanks a lot
Thanks!
Thank you so much!
GOAT
thank you
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.
can some one explain what happens if i==m and j
Thanks
Can someone explain why we dont add cache for line 11 & line 13 the two base cases?
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..
Could you explain wildcard matching, a similar problem to this one?
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.
what if s reaches the end but p does not? That will not always return a true right? Where did we cover that case?
@NeetCode can you do validate binary tree nodes next? Leetcode 1361
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!
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!
+1
this is called Codeagasm. Mind blowing.
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.
this algorithm is not working for case s="aa" and p="*". since its checking for j+1 for * its not working..
recursion & caching 😊
Can someone explain to me how the aab == c*a*b? Isn't it suppose to cover the entire string?
This was the best explanation ever, but I have a doubt. At 18:45 you said its no problem if i is out of bounds and j isn't. But what if for a string S = a, the pattern is P = a*b. In this case, they do not match? Thanks in advance! Really appreciate it.
Yes you're right that those strings don't match, but the function will continue I think and eventually return false in that case.
For example, in P, there is a remaining b, but the function doesn't yet know if that is a mandatory b, or if it's a b*, because b* means that the b is not mandatory.
@@NeetCode thanks bud got it
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
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?