# Python solution with detailed explanation

• Solution

Distinct Subsequences https://leetcode.com/problems/distinct-subsequences/?tab=Description

Question

Dynamic Programming

``````class Solution(object):
def numDistinct(self, s, t):
"""
:type s: str
:type t: str
:rtype: int
"""
N, M = len(t), len(s)
dp = [[0]*(M+1) for _ in range(N+1)]
for i in range(N+1):
dp[i][0] = 0    # How many subsequences of zero length S can be formed which equal t[0:i]
for j in range(M+1):
dp[0][j] = 1    # How many subsequences of S[0:j] can be formed which equal t[0:1]
for i in range(1, N+1):
for j in range(1, M+1):
if t[i-1] == s[j-1]:
dp[i][j] = dp[i-1][j-1] + dp[i][j-1]
else:
dp[i][j] = dp[i][j-1]
return dp[N][M]
``````

Memoization

``````from collections import defaultdict
class Solution(object):
def helper(self, i, j, s, t, cache):
if i == len(s) and j == len(t):
return 1
elif i == len(s):
return 0
elif j == len(t):
return 1
elif i in cache and j in cache[i]:
return cache[i][j]
elif s[i] == t[j]:
# Include or Do Not Include
return self.helper(i+1, j+1, s, t, cache) + self.helper(i+1, j, s, t, cache)
else:
return self.helper(i+1, j, s, t, cache)

def numDistinct(self, s, t):
"""
:type s: str
:type t: str
:rtype: int
"""
cache = defaultdict(dict)
return self.helper(0,0,s,t,cache)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.