• Time:O(mn)
• Space:O(mn)

## C++

``````class Solution {
public:
int numDistinct(string s, string t) {
const int m = s.length();
const int n = t.length();
vector<vector<long>> dp(m + 1, vector<long>(n + 1));

for (int i = 0; i <= m; ++i)
dp[i][0] = 1;

for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
if (s[i - 1] == t[j - 1])
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
else
dp[i][j] = dp[i - 1][j];

return dp[m][n];
}
};
``````

## JAVA

``````class Solution {
public int numDistinct(String s, String t) {
final int m = s.length();
final int n = t.length();
long[][] dp = new long[m + 1][n + 1];

for (int i = 0; i <= m; ++i)
dp[i][0] = 1;

for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
if (s.charAt(i - 1) == t.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
else
dp[i][j] = dp[i - 1][j];

return (int) dp[m][n];
}
}
``````

## Python

``````class Solution:
def numDistinct(self, s: str, t: str) -> int:
m = len(s)
n = len(t)
dp = [[0] * (n + 1) for _ in range(m + 1)]

for i in range(m + 1):
dp[i][0] = 1

for i in range(1, m + 1):
for j in range(1, n + 1):
if s[i - 1] == t[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j]

return dp[m][n]
``````

• Time:O(mn)
• Space:O(n)

## C++

``````class Solution {
public:
int numDistinct(string s, string t) {
const int m = s.length();
const int n = t.length();
vector<long> dp(n + 1);
dp[0] = 1;

for (int i = 1; i <= m; ++i)
for (int j = n; j >= 1; --j)
if (s[i - 1] == t[j - 1])
dp[j] += dp[j - 1];

return dp[n];
}
};
``````

## JAVA

``````class Solution {
public int numDistinct(String s, String t) {
final int m = s.length();
final int n = t.length();
long[] dp = new long[n + 1];
dp[0] = 1;

for (int i = 1; i <= m; ++i)
for (int j = n; j >= 1; --j)
if (s.charAt(i - 1) == t.charAt(j - 1))
dp[j] += dp[j - 1];

return (int) dp[n];
}
}
``````

## Python

``````class Solution:
def numDistinct(self, s: str, t: str) -> int:
m = len(s)
n = len(t)
dp = [1] + [0] * n

for i in range(1, m + 1):
for j in range(n, 1 - 1, -1):
if s[i - 1] == t[j - 1]:
dp[j] += dp[j - 1]

return dp[n]
``````