# 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
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][0] = 1 # 1 way for anything to match an empty string
for i in range(1, len(match)):
for j in range(1, len(match[0])):
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[0][0] = 1;
for (int i = 1; i <= nT; ++i)
res[i][0] = 0;
for (int i = 1; i <= nS; ++i)
res[0][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];
}
};