Python Recursive(MLE) and Iterative Answers with Explanation

  • 0

    As with all questions relating to the sub sequence, we can either pick an element in our current index, or continue without it.

    If we create T, then that's one distinct subsequence (which is dictated by the combination of indexes picked).

    So we have two options, to pick the item or not pick the item, and by adding the two ways, we will get all possible combinations of indexes picked in 2^N.

    class Solution(object):
        def numDistinct(self, s, t):
            return self.count(s,t, 0, 0, '', dict())
        def count(self, s, t, sidx, tidx, curr, cache):
            if tidx == len(t):
                return 1
            if sidx == len(s):
                return 1 if curr == t else 0
            if (sidx, tidx) in cache:
                return cache[(sidx, tidx)]
            with_el = 0
            if s[sidx] == t[tidx]:
                with_el = self.count(s, t, sidx+1, tidx+1, curr+s[sidx], cache)
            without_el = 0
            without_el = self.count(s, t, sidx+1, tidx, curr, cache)
            cache[(sidx,tidx)] = with_el + without_el
            return cache[(sidx,tidx)]

    We can also solve this problem using tabulation in O(T*S) in a similar fashion to our recursive solution.

    The key to note is that dp[i][j] = dp[i-1][j-1] + dp[i-1][j] which tells us the same information as the recursive solution does, for choosing this element, and not choosing this element.

    class Solution(object):
        def numDistinct(self, s, t):
            if len(s) == 0 or len(t)>len(s):
                return 0
            dp = [[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
            for i in range(len(dp)):
                for j in range(len(dp[0])):
                    if i == 0 and j == 0:
                        dp[i][j] = 1
                    elif i == 0:
                        dp[i][j] = 0
                    elif j == 0:
                        dp[i][j] = 1
                    elif t[j-1] != s[i-1]:
                        dp[i][j] = dp[i-1][j]
                    elif t[j-1] == s[i-1]:
                        dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
            return dp[-1][-1]

Log in to reply

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