A really easy optimization that can be added is to check if there are enough characters left in s to create t, this can be done as easily as: if len(s) - i < len(t) - j: return 0. Improves runtime significantly
@@hetanthakkar5066 I think it just comes down to understanding the code and seeing if there are any obvious deficiencies. When I noticed this optimization, I probably was looking for ways to know when we were done
i can't believe i solved a hard on my own in like 10 minutes, but its all thanks to your 1-D and 2-D DP guides, the patterns start to emerge and this suddenly becomes simple
slight optimization: Instead of returning 0 if i == len(s), we can return 0 earlier by checking if len(s) - i < len(t) - j, which means that the rest of s is too small for the rest of t.
Hey NeetCode, I think there’s a typo on line 14/16 where we’re moving the i pointer forward but not the j pointer - it should be dfs(i + 1, j) instead correct? And thanks again for another great video!
Great video, was able to write this after watching! class Solution: def numDistinct(self, s: str, t: str) -> int: @cache def dp( i, j ) -> int: if j == len( t ): return 1 if i == len( s ): return 0
res = dp( i+1, j ) if s[i] == t[j]: res += dp( i+1, j+1 ) return res
i dont usually comment on videos but EXCELLENT video, short, crisp and to the point ! here's the java version class Solution { int[][] cache; public int numDistinct(String s, String t) { if(s.length() == 0) return 0; else if(t.length() == 0) return 1; cache = new int[s.length()+1][t.length()+1]; for(int[] arr : cache) Arrays.fill(arr, -1); return dfs(s, t, 0, 0); } public int dfs(String s, String t, int x, int y){ if(y == t.length()) return 1; else if(x == s.length()) return 0; else if(cache[x][y] != -1) return cache[x][y]; int ans = 0; if(s.charAt(x) == t.charAt(y)) ans += dfs(s,t,x+1,y+1) + dfs(s,t,x+1,y); else ans += dfs(s,t,x+1,y); return cache[x][y] = ans; } }
We can add a optimization as first line in the dfs function if (len(t)-j) > (len(s)-i): return 0 As there is no valid matching when length of t to be matched is greater than the characters left in string s
Hey, Thanks for the explanation but I think in the solution it will be `if s[i] == t[j]: cache[(i,j)] = dfs(i+1,j+1) + dfs(i+1,j) else: cache[(i,j)] = dfs(i+1,j)`
Hey Navdeep(@Neetcode), just a small suggestion , May be for the sake of future viewers ,you could fix the typo(i + i) in line 14, may be any kind of overlay on video should do i guess
It's so simple, really appreciate your work, I wrote a solution for this one but having some trouble with memoization, need some advice: count = 0 def check(sub, i, length): nonlocal count if i>=n: return if length>m: return if sub!=t[:length]: return if sub==t: count+=1 return
for j in range(i+1,n): temp = sub sub+=s[j] check(sub, j, length+1) sub = temp
for i in range(n): check(s[i], i, 1) return count n and m are lengths of s and t respectively
Interestingly, when implementing this in JavaScript with a Map, I only get to question 53/65 before the time limit exceeds, even when I use the optimizations listed in the comments.
HI! what age did you start programming and how long did it take you to be able to solve most of these questions? im 14 i started 2 months ago and im able to solve most of leetcode's problems but i kinda struggle with dynamic problems thanks!
It's a perfect age, the sooner the better. I would say that your struggling will be solved with practice. Just don't give up and you will succeed in programming
I've got this solution but I thought it's only a backtrack approach. I assumed there must be another dp solution where we use some kind of table like, for instance, in longest subsequence
It could be even O(s) space. Runtime beats 90% and memory beats 90%: dp = [1] * (len(s) + 1) for i in range(len(t)): newRow = [0] for j in range(len(s)): if t[i] == s[j]: newRow.append( newRow[j] + dp[j] ) else: newRow.append( newRow[j]) dp = newRow return dp[len(s)]
How do I know when to use like a table dp approach and when to use this recursive with memoization. I really am confused. The recursive is so much easier but it almost always TLEs on leetcode even with memoization.
every single DP problem can be solved using both recursive (top down approach) and tabulation (bottom up approach). its just that some problems are easy to write in recursive form and some are easy to write in tabulation form. but the confusion will stop only when you actually understand why tabulation form works in every single problem. patterns in tabulation form differs more than recursive form hence recursive is easy. but you can learn few patterns in tabulation form thoroughly (best way is debug each step in tabulation form then you will understand easily ) then you can understand most of the problems
To take care of the situation when both the i and j ended together since j ended this possible sequence needs to be counted but if you return for the i first it will be 0 hence the formed string will not be counted so we need to check before if j ended and return 1 as required.
Hey NeetCode, I tested this solution for some of the inputs and it didn't output the right answer. Eg: 1. Let s="babgbag" t= "bag"; The output of the program is 2 while the expected output is 5. 2. Let s="rabbbit" t="rabbit"; The output of the program is 1 while the expected output is 3. Kindly look into it.
hi can anyone explain this if (s[i] == t[j]) { dp[{i, j}] = dfs(s, t, i + 1, j + 1) + dfs(s, t, i + 1, j); } else { dp[{i, j}] = dfs(s, t, i + 1, j); } insted of this can I do int ans=0; for(int z = i;z
💡 DP PLAYLIST: ua-cam.com/video/73r3KWiEvyk/v-deo.html
Hey @NeetCode, where all do you prefer using a hasmap to a 2D array?
Watching this at 1 am. I’m more addicted to you playlist than Netflix.
I'm looking forward, one day Netflix will buy the Neetcode's DP playlist and film it.
There's just something so peaceful about these videos
A really easy optimization that can be added is to check if there are enough characters left in s to create t, this can be done as easily as: if len(s) - i < len(t) - j: return 0.
Improves runtime significantly
damn youre right! went from 7% to 98% lol. good catch
Apart from this trick, How do you come up with such optimization? any specific pointers would help for further problems
@@hetanthakkar5066 I think it just comes down to understanding the code and seeing if there are any obvious deficiencies. When I noticed this optimization, I probably was looking for ways to know when we were done
@@themagickalmagickman got it.Thank you for the explanation.
Just did this problem and also though of this optimization, it increased my runtime from 32ms to 10ms. Glad to see someone else did the same! :)
i can't believe i solved a hard on my own in like 10 minutes, but its all thanks to your 1-D and 2-D DP guides, the patterns start to emerge and this suddenly becomes simple
Men you always save me i almost solved 200 problem in leetcode, and now i start solving DP problems, thank you.
slight optimization: Instead of returning 0 if i == len(s), we can return 0 earlier by checking if len(s) - i < len(t) - j, which means that the rest of s is too small for the rest of t.
Hey NeetCode, I think there’s a typo on line 14/16 where we’re moving the i pointer forward but not the j pointer - it should be dfs(i + 1, j) instead correct?
And thanks again for another great video!
Oh crap... Good catch! You're right, it should be "+ 1" not "+ i", thanks for letting me know!
I was searching the comment section for someone who commented on it :D
@@Hiroki-Takahashi me to
Great video, was able to write this after watching!
class Solution:
def numDistinct(self, s: str, t: str) -> int:
@cache
def dp( i, j ) -> int:
if j == len( t ):
return 1
if i == len( s ):
return 0
res = dp( i+1, j )
if s[i] == t[j]:
res += dp( i+1, j+1 )
return res
return dp( 0, 0 )
i dont usually comment on videos but EXCELLENT video, short, crisp and to the point !
here's the java version
class Solution {
int[][] cache;
public int numDistinct(String s, String t) {
if(s.length() == 0)
return 0;
else if(t.length() == 0)
return 1;
cache = new int[s.length()+1][t.length()+1];
for(int[] arr : cache) Arrays.fill(arr, -1);
return dfs(s, t, 0, 0);
}
public int dfs(String s, String t, int x, int y){
if(y == t.length())
return 1;
else if(x == s.length())
return 0;
else if(cache[x][y] != -1)
return cache[x][y];
int ans = 0;
if(s.charAt(x) == t.charAt(y))
ans += dfs(s,t,x+1,y+1) + dfs(s,t,x+1,y);
else
ans += dfs(s,t,x+1,y);
return cache[x][y] = ans;
}
}
We can add a optimization as first line in the dfs function
if (len(t)-j) > (len(s)-i): return 0
As there is no valid matching when length of t to be matched is greater than the characters left in string s
big boost in ex. time on leet
Good one!
in the question, there is 1 constraint:
1
Hey, Thanks for the explanation but I think in the solution it will be
`if s[i] == t[j]:
cache[(i,j)] = dfs(i+1,j+1) + dfs(i+1,j)
else:
cache[(i,j)] = dfs(i+1,j)`
That looks correct, not sure why nobody else said this
I really like the transition modelling visualization, Thanks for such brilliant explanantion!
Hey Navdeep(@Neetcode), just a small suggestion , May be for the sake of future viewers ,you could fix the typo(i + i) in line 14, may be any kind of overlay on video should do i guess
It's so simple, really appreciate your work, I wrote a solution for this one but having some trouble with memoization, need some advice:
count = 0
def check(sub, i, length):
nonlocal count
if i>=n:
return
if length>m:
return
if sub!=t[:length]:
return
if sub==t:
count+=1
return
for j in range(i+1,n):
temp = sub
sub+=s[j]
check(sub, j, length+1)
sub = temp
for i in range(n):
check(s[i], i, 1)
return count
n and m are lengths of s and t respectively
1D, DP solution
def numDistinct(self, s: str, t: str) -> int:
dp = [1] * (len(s) + 1)
for j in range(len(t)- 1, -1, -1):
nextDP = [0] * (len(s) + 1)
for i in range(len(s) - 1, -1, -1):
if s[i] == t[j]:
nextDP[i] = nextDP[i + 1] + dp[i + 1]
else:
nextDP[i] = nextDP[i + 1]
dp = nextDP
return dp[0]
And it is pretty efficient.
Wonderful! Will definitely watch your dp series.
Interestingly, when implementing this in JavaScript with a Map, I only get to question 53/65 before the time limit exceeds, even when I use the optimizations listed in the comments.
Your channel is GOLD !!!!
such a neat and to a point solution keep it up👍👍👍
you made the world super simple again
Clean Explanation
Hi, I am confused with the difference between ' dynamic programming ' and ' dfs + cache"
DFS means recursive solution
DFS+memorization==recursion+memoization
Very Nice Explanation ...Thankyou
there is a true DP approach using just O(N) space that beats 85% on LeetCode.
class Solution:
def numDistinct(self, s: str, t: str) -> int:
prevDP = [0] * (len(t) + 1)
prevDP[-1] = 1
for i in range(len(s) - 1, -1, -1):
currDP = [0] * (len(t) + 1)
currDP[-1] = 1
for j in range(len(t) - 1, -1, -1):
if s[i] == t[j]:
currDP[j] = prevDP[j] + prevDP[j + 1]
else:
currDP[j] = prevDP[j]
prevDP = currDP
return prevDP[0]
HI! what age did you start programming and how long did it take you to be able to solve most of these questions?
im 14 i started 2 months ago and im able to solve most of leetcode's problems but i kinda struggle with dynamic problems thanks!
It's a perfect age, the sooner the better. I would say that your struggling will be solved with practice. Just don't give up and you will succeed in programming
@@ZQutui thanks I sure will!
I've got this solution but I thought it's only a backtrack approach. I assumed there must be another dp solution where we use some kind of table like, for instance, in longest subsequence
class Solution:
def numDistinct(self, s: str, t: str) -> int:
cache = {}
def dfs(i,j):
if j==len(t):
return 1
if i==len(s):
return 0
# if i==len(s) or j==len(t):
# return int(j==len(t))
if (i,j) in cache:
return cache[(i,j)]
if s[i]==t[j]:
cache[(i,j)] = dfs(i+1,j+1)+dfs(i+1,j)
else:
cache[(i,j)] = dfs(i+1,j)
return cache[(i,j)]
return dfs(0,0)
There is a huge change when we don't write the base cases in order ; incase we interchange the base case orders we get wrong output!!!!!!!
oh shit thanks!
simple and clear! thanks !!!
Time limit exceeds, you need to do memoization...
Thank you!
This solution leads to Time Limit Exceeded on Leetcode.
First hard problem i solved
It could be even O(s) space. Runtime beats 90% and memory beats 90%:
dp = [1] * (len(s) + 1)
for i in range(len(t)):
newRow = [0]
for j in range(len(s)):
if t[i] == s[j]:
newRow.append( newRow[j] + dp[j] )
else:
newRow.append( newRow[j])
dp = newRow
return dp[len(s)]
This isn’t dp, right? It’s memoisation (i.e DFS + Hash map)
DP is an approach to solve recursive problems wherein the overlapping sub-problems are only executed once. So yes when we use memoisation, this is DP.
Neetcode Nagaraj
How do I know when to use like a table dp approach and when to use this recursive with memoization. I really am confused. The recursive is so much easier but it almost always TLEs on leetcode even with memoization.
every single DP problem can be solved using both recursive (top down approach) and tabulation (bottom up approach). its just that some problems are easy to write in recursive form and some are easy to write in tabulation form. but the confusion will stop only when you actually understand why tabulation form works in every single problem. patterns in tabulation form differs more than recursive form hence recursive is easy. but you can learn few patterns in tabulation form thoroughly (best way is debug each step in tabulation form then you will understand easily ) then you can understand most of the problems
Can someone explain why we must first examine if j reaches string t's end?
To take care of the situation when both the i and j ended together since j ended this possible sequence needs to be counted but if you return for the i first it will be 0 hence the formed string will not be counted so we need to check before if j ended and return 1 as required.
and liked this video as always. big THX
so clear!
Love it !
Hey NeetCode, I tested this solution for some of the inputs and it didn't output the right answer.
Eg: 1. Let s="babgbag" t= "bag"; The output of the program is 2 while the expected output is 5.
2. Let s="rabbbit" t="rabbit"; The output of the program is 1 while the expected output is 3.
Kindly look into it.
Probably because you're checking S[I] == S[J] instead of S[I] == 'T'[J].. 2 years late but hey better late than never :)
combination sum ???
Combination Sum IV? I can try to do it soon
@@NeetCode Thanks
Why is the complexity M*N?
Needs a better explanation.
Perfect
hi can anyone explain this
if (s[i] == t[j]) {
dp[{i, j}] = dfs(s, t, i + 1, j + 1) + dfs(s, t, i + 1, j);
} else {
dp[{i, j}] = dfs(s, t, i + 1, j);
}
insted of this can I do
int ans=0;
for(int z = i;z
Excellenrtrrtttttt😮
awesome