Python solution with detailed explanation


  • 0
    G

    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)
    

Log in to reply
 

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