Distinct Subsequences

Problem Link: https://leetcode.com/problems/distinct-subsequences/

Recursion

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        
        def recursion(s,t,i,j):
            if(j<0):
                return 1
            if(i<0):
                return 0
            
            if(s[i]==t[j]):
                consider=recursion(s,t,i-1,j-1)
                reject=recursion(s,t,i-1,j)
                return consider+reject
            else:
                reject=recursion(s,t,i-1,j)
                return reject
        
        i=len(s)-1
        j=len(t)-1                
        ans = recursion(s,t,i,j)
        return ans

Tabulation

class Solution:
    def numDistinct(self, s: str, t: str) -> int:        
        m=len(s)
        n=len(t)
        dp=[[0 for i in range(n+1)] for j in range(m+1)]
        for i in range(m+1):
            for j in range(n+1):
                if(i==0):
                    dp[i][j]=0
                if(j==0):
                    dp[i][j]=1    
                else:
                    if(s[i-1]==t[j-1]):
                        consider=dp[i-1][j-1]
                        reject=dp[i-1][j]
                        dp[i][j]=consider+reject
                    else:
                        dp[i][j]=dp[i-1][j]
        return dp[m][n]