115. Distinct Subsequences

115. Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Example 1:

Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:

As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

Example 2:

Input: S = "babgbag", T = "bag"
Output: 5
Explanation:

As shown below, there are 5 ways you can generate "bag" from S.
(The caret symbol ^ means the chosen letters)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^

Solution 1

# code 1
import functools
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        @functools.lru_cache(None)
        
        def swaps(i, j):
            if j == len(t):
                return 1
            
            if i == len(s):
                return 0
            
            temp = 0
            
            if s[i] == t[j]:
                temp += swaps(i+1, j+1)
            
            temp += swaps(i+1, j)
            
            return temp
        return swaps(0, 0 )

Solution 2

#code 2
class Solution:
    def numDistinct(self, s, t):
        
        m, n = len(s), len(t)
        
        dp = [[0] * (n+1) for _ in range(m+1)]
        
        for i in range(n+1):
            dp[0][i] = 0
        
        for j in range(m+1):
            dp[j][0] = 1
        
        def get_value():
            
            for i in range(1,m+1):
                for j in range(1, n+1):
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-1]*(s[i-1] == t[j-1])
            return dp[m][n]
        
        return get_value()

Solution 3

#code 3
class Solution:
    def numDistinct(self, s, t):
        m, n = len(s), len(t)
        dp = [0]*(n+1)
        dp[0] = 1
        
        for i in range(1,m+1):
            for j in range(n, 0 , -1):
                dp[j] = dp[j] + dp[j-1]*(s[i-1] == t[j-1])
        
        return dp[n]

Solution 4

#not my solution, but it works fine
class Solution:
    def numDistinct(self, s: 'str', t: 'str') -> 'int':
        chars, index, dp = set(t), collections.defaultdict(list), [0] * len(t)
        for i, c in enumerate(t):
            index[c].append(i)
        for c in s:
            if c in chars:
                for i in index[c][::-1]:
                    print(index[c][::-1])
                    dp[i] += dp[i - 1] if i > 0 else 1
                    print(dp)
        return dp[-1]