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
    ^^^

Difficulty: interview

Starter code:

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        

Solutions:
class Solution:
     def numDistinct(self, s, t):
         """
         :type s: str
         :type t: str
         :rtype: int
         """
         setOft=set(t)
         news=""
         for ch in s:
             if ch in setOft:
                 news+=ch
         dp=[[1 for i in range(len(news)+1)] for j in range(len(t)+1)]
         for j in range(1,len(t)+1):
             dp[j][0]=0
 
         for i in range(len(t)):
             for j in range(len(news)):
                 if t[i]==news[j]:
                     dp[i+1][j+1]=dp[i][j]+dp[i+1][j]
                 else:
                     dp[i+1][j+1]=dp[i+1][j]
         return dp[len(t)][len(news)]


class Solution:
     def __init__(self):
         self.dp = {}
         self.s = ""
         self.t = ""
         self.letter2Indices = {}
     
     def numDistinct(self, s, t):
         """
         :type s: str
         :type t: str
         :rtype: int
         """
         if len(s) < len(t):
             return 0
         if not t:
             return 1
         
         self.s = s.lower()
         self.t = t.lower()
         length = len(s)
         for i in range(len(t)):
             self.dp[i] = [-1] * length
         for i in range(length):
             letter = self.s[i]
             if letter in self.letter2Indices:
                 self.letter2Indices[letter].append(i)
             else:
                 self.letter2Indices[letter] = list([i])
             
         return self.numSubseq(0, 0)
     
     def numSubseq(self, startS, startT):
         if startT >= len(self.t):
             return 1
         if startS >= len(self.s):
             return 0
         
         if self.dp[startT][startS] >= 0:
             return self.dp[startT][startS]
         
         letter = self.t[startT]
         count = 0
         firstMatch = -1
         if letter in self.letter2Indices:
             for i in self.letter2Indices[letter]:
                 if i >= startS:
                     count += self.numSubseq(i+1, startT+1)
                     if firstMatch < 0:
                         # We can directly fill dp[startT][startS:firstMatch-1] with the same number
                         firstMatch = i
                     
         self.dp[startT][startS] = count
         for i in range(startS + 1, firstMatch):
             self.dp[startT][i] = count
         return count
         
         
         
         
         
         
         
         


class Solution:
     def numDistinct(self, s, t):
         """
         :type s: str
         :type t: str
         :rtype: int
         """
         result = (len(t) + 1) * [0]
         result[0] = 1
         for j in range(len(s)):
             for i in reversed(range(len(t))):
                 if s[j] == t[i]:
                     result[i + 1] += result[i]
         return result[-1]

class Solution:
     def numDistinct(self, s, t):
         """
         :type s: str
         :type t: str
         :rtype: int
         """
         row = len(s) + 1
         col = len(t) + 1
         dp = [0]*col
         dp[0] = 1
         for i in range(1, row):
             pre = dp[:]
             # print(pre)
             for j in range(1, col):
                 if s[i-1] == t[j-1]:
                     dp[j] += pre[j-1]
             # print(dp)
         return dp[-1]
                     


class Solution:
     def numDistinct(self, s, t):
         """
         :type s: str
         :type t: str
         :rtype: int
         """
         if len(s) < len(t):
             return 0
         dp = [0] * len(s)
         for i in range(len(s)):
             dp[i] = dp[i-1] if i > 0 else 0
             if s[i] == t[0]:
                 dp[i] += 1
                 
         for i, ti in enumerate(t[1:]):
             dp2 = [0] * len(s)
             for j in range(i+1, len(s)):
                 dp2[j] = dp2[j-1]
                 if s[j] == ti:
                     dp2[j] += dp[j-1]
             dp = dp2
         return dp[-1]