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 TH-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.
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!
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.
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
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
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 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
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.
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.
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.
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
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??
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
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.
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!
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!
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.
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?
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?🤔
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.
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.
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?
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*"
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
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?
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.
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.
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
![ไข้ขึ้นเลย! เมื่อแฝดโดนจัดเต็มวัคซีนครบ2เดือน🤒 [cc] แดนแพทตี้ SS2 | EP.54 |](http://i.ytimg.com/vi/z2VHItnyyvY/mqdefault.jpg)
Dynamic Programming Playlist: th-cam.com/video/73r3KWiEvyk/w-d-xo.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 TH-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.
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!
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??
😅
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?
Thanks this is very helpful
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
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 :)
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
you need to explain how the cache actually saves time. How does storing the indexes along with a bool value save any time?
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)
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?
The clearest explanation I've seen!!! You are awesome :)
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
Great explanation! You explained the algorithm very clearly. I'm not even Python guy, but I still liked your video!
Simply mind-blowing explanation, you made it so simple!! Thanks you! Please keep up the good work!
This explanation makes the whole process clean and simple.
The dramatic decrease in time taken to execute after using cache surprised me .
Thanks for the explanation and code
This is a fabulous and thorough explanation. The decision tree explanation and visual for the asterisk was what did it for me. Thank you!
great explanation .....also the vibe of ur videos is relaxing!
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.
How easy you make a hard problem is unbelievable !!!!!! Salute to you
I was struggling a lot with this question. Your video cleared my doubts. Thanks for sharing!
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.
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, Neet! Great Explanation!
BEST EXPLANATIONS ARE HERE :)
Thank you so much for these quality videos!
Wow man your explanation is just fantastic!
You make hard problems very easy. Thanks for explaining.
What a brilliant solution and in-depth explanation for this seriously hard problem !!! WOW .... Thank you !!!!
this problem took me soo much time to understand, thank you dude
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
Wow so much easier to understand than the DP solution! Thanks for showing your mistakes as well
i seriously love your video i swear you dont waste time i love it
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??
You made it look so simple. Thank you!
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
You make this question easy to udnerstand. Thank you for all your amazing solutions!!
WTF !! Bro
You made clear in just 20 minutes🤩
The base case can be simplified with
if j == n:
return i == m
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.
the question description feels really incomplete without your explanation , thanks a lot
just a clean explanation amazing
I really appreciate your explanation, so clean, so logical!
Perfect explanation! Thank you. And the code looks good.
What an explanation sir ji❤. After this, I was able to solve wildcard matching by myself.
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
A correction:
if j>=len(p): return i >= len(s) # If pattern is exhausted, return True only if string is also exhausted
This question makes me appreciate the hard work of people who have created the full-blown regex.
Thank you for the explanation. I thought according to the problem statement, 'c*' cannot be empty, which was very misleading by Leetcode.
man love ur explanation ,great man ,no words love u man
Very good explanation, love the channel!
i checked so many videos of this problem.. but there's simply no compedition to you bro. keep the neet work up bro/>
Best explanation ever found for this problem.
by switching "use" and "don't use" in or return statement you can significantly cut complexity down even without memoization
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!
Wow! You made it look like a piece 'o cake. Thanks, I really appreciate it.
Excellent work. Earned a sub. Keep it up.
thnks bro i was not getting how to solve this , this is same as wildcard matching with a twist
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.
Great explanation! :) @NeetCode what tool do you use to write and draw ?
Any specific brand, I'm looking for this kind of tools
Thanks. its a pretty difficult problem.
Super awesome explanation NeetCode 🎉Thanku
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?
Periods must represent a character, they can't be an empty string, only the star can be an empty string.
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.
Very good explanation thanks!
leet code accepting if 6th line change to j>len(p) instead of j>=len(p)
Thanks!
Thank you so much!
can some one explain what happens if i==m and j
Awesome explanation. Thank you so much
Thank you! this is owesome!
Appreciate your explanation thank you
thank god for this guy i was STUCK
I loved it man, thanks a lot :)
Super thanks for this!
Great video and explanation thank you!
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 a legend.
Amazing explanation!
Best explanation ever!
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?🤔
Amazing explanation .. Really thankful for your great efforts.. :)
Glad it was helpful!
Thank you for the very good video
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.
Great video!!!! Thank you!
Best explanations! Thank you!
Thanks 😊
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
The best explanation!!!
Thanks for great explain! Do you also have an explain on complexity analysis of this recursive call? Thank you!
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?
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*"
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
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?
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.
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.
This was perfect!
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
you are talented
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!
Hey what would be the Time and Space complexity ? Backtracking with memoization means 2^n?
this is called Codeagasm. Mind blowing.
Great one. Thanks.
Awesome mate!