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 RU-vid 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
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
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.
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??
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.
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)
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.
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.
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.
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
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!
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?
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
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!
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*"
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) 🤔
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...
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.
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.
"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."
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?🤔
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..
