[LeetCode] 115. Distinct Subsequences

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

Use helper(i, j) method to calculate number of sequence of S[0:i] equals T[0:j]

j == 0  means target string is empty.  Then return 1 as there always 1 subsequence equals to empty target string;

i == 0 means source string is empty. Then return 0 as cannot find subsequence for non-empty target string.

if S[i-1] ==  T[j-1],  there are 2 options to get target string:

1.  Use S[i-1] to match T[j-1].  Number of sequence = helper(i-1, j-1)

2.  Skip S[i-1].   Number of sequence = helper(i-1, j)

If S[i-1] != T[j-1],  there is only 1 option:

Skip S[i-1].  Number of sequence = helper(i-1, j)

Time Complexity = O ( M * N ),   M = len(S),  N = len(T)

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        
        @cache
        def helper(i, j):
            if i >= len(s) or j >= len(t):
                return 1 if j == len(t) else 0
            
            if s[i] == t[j]:
                return helper(i+1, j+1) + helper(i+1, j)
            
            return helper(i+1, j)
        
        return helper(0, 0)

Bottom-up solution :

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        M = len(s)
        N = len(t)
        
        dp = [[0] * (N+1) for _ in range(M+1)]
        
        for i in range(M):
            dp[i+1][N] = 1 if s[i] == t[N-1] else 0
        
        for i in reversed(range(M)):
            for j in reversed(range(N)):
                if s[i] == t[j]:
                    dp[i][j] = dp[i+1][j+1] + dp[i+1][j]
                else:
                    dp[i][j] = dp[i+1][j]
    
        return dp[0][0]

Edited of 09/19/2021. Add the bottom-up solution.