Distinct Subsequences - Dynamic Programming - Leetcode 115 - Python

0:00 - Read the problem
1:05 - Drawing Explanation
9:00 - Coding Explanation

leetcode 115

#twitter #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[themagickalmagickman]

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

[nikhil]

Watching this at 1 am. I’m more addicted to you playlist than Netflix.

[bernardpark]

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!

[BJACK]

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 )

[JLJConglomeration]

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

[yassineacherkouk]

Men you always save me i almost solved 200 problem in leetcode, and now i start solving DP problems, thank you.

[sk_]

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.

[phaninag]

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

[kartikeyrana]

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
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;
}
}

[runzsh]

I really like the transition modelling visualization, Thanks for such brilliant explanantion!

[rishabhsinha]

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)`

[hoyinli]

in the question, there is 1 constraint:

1 <= s.length, t.length <= 1000

[aryanyadav]

Wonderful! Will definitely watch your dp series.

[homyakMilashka]

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.

[sumeetbisen]

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

[aradog]

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!

[kuangyimeng]

Hi, I am confused with the difference between ' dynamic programming ' and ' dfs + cache"

[DeGoya]

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

[pritampawar]

such a neat and to a point solution keep it up👍👍👍

[danielsun]

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.