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

Approach 1: DP.

### # Code (Python)

Approach 1:

``````    def numDistinct(self, s: str, t: str) -> int:
# match[i][j]: ways for the first i chars in s to match the first j chars in t
match = [[0 for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]
for i in range(len(match)):
match[i] = 1 # 1 way for anything to match an empty string

for i in range(1, len(match)):
for j in range(1, len(match)):
if s[i-1] != t[j-1]:
match[i][j] = match[i-1][j] # use the previous portion of s to match t
else:
match[i][j] = match[i-1][j] + match[i-1][j-1] # in addition, match the last char of s to the last char of t

return match[-1][-1]
``````

### # Code (C++)

Approach 1:

``````// DP - 2D.
class Solution {
public:
int numDistinct(string s, string t) {
int nS = s.size();
int nT = t.size();
if (nS < nT)
return 0;
long res[nT+1][nS+1];
res = 1;
for (int i = 1; i <= nT; ++i)
res[i] = 0;
for (int i = 1; i <= nS; ++i)
res[i] = 1;
for (int i = 1; i <= nT; ++i)
{
for (int j = i; j <= nS; ++j)
{
res[i][j] = 0;
if (j > i)
res[i][j] += res[i][j-1];
if (t[i-1] == s[j-1])
res[i][j] += res[i-1][j-1];
}
}
return res[nT][nS];
}
};

// DP - 1D.
class Solution {
public:
int numDistinct(string s, string t) {
int nS = s.size();
int nT = t.size();
if (nS < nT)
return 0;
vector<long> res(nS+1, 0);
for (int i = 0; i <= nS; ++i)
res[i] = 1;
for (int i = 1; i <= nT; ++i)
{
vector<long> prev = res;
for (int j = i; j <= nS; ++j)
{
res[j] = 0;
if (j > i)
res[j] += res[j-1];
if (t[i-1] == s[j-1])
res[j] += prev[j-1];
}
}
return res[nS];
}
};
``````