Problem statement

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

Solution

Dynamic programming problem, where dp[i][j] is the number of subsequences of S[0:i], equal to T[0:j]. Then to evaluate dp(i, j) we need to look at two options:

  1. dp(i - 1, j): if we do not include the symbol s[i].
  2. dp(i - 1, j - 1) if we include it but it is only for the case when s[i] == t[j].

Complexity

Time complexity is O(mn), space complexity as well.

Code

class Solution:
    def numDistinct(self, s, t):
        @lru_cache(None)
        def dp(i, j):
            if i == -1: return j == -1
            if j == -1: return j == -1
            return dp(i-1, j) + (s[i] == t[j]) * dp(i-1, j-1)
            
        return dp(len(s) - 1, len(t) - 1)