## Algorithm

Problem Nmae: 115. Distinct Subsequences

Given two strings `s` and `t`, return the number of distinct

of `s` which equals `t`.

The test cases are generated so that the answer fits on a 32-bit signed integer.

Example 1:

```Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from s.
`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.
`babgbag` `babgbag` `babgbag` `babgbag` `babgbag````

Constraints:

• `1 <= s.length, t.length <= 1000`
• `s` and `t` consist of English letters

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

int numDistinct(char* s, char* t) {
if (s == NULL || t == NULL) return 0;
int n = strlen(s);
int m = strlen(t);

int (*dp)[n] = (int (*)[n])calloc(n * m, sizeof(int));
int i, j;

dp[0][0] = (t[0] == s[0] ? 1 : 0);

for (j = 1; j < n; j++) {
dp[0][j] = dp[0][j - 1] + (t[0] == s[j] ? 1 : 0);
}

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

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

int ans = dp[m - 1][n - 1];
free(dp);

return ans;
}

int main() {
char s[] = "acaaca";
char t[] = "ca";

assert(numDistinct(s, t) == 4);

printf("all tests passed!\n");

return 0;
}
``````
Copy The Code &

Input

cmd
s = "rabbbit", t = "rabbit"

Output

cmd
3

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const numDistinct = function(s, t) {
const tlen = t.length
const slen = s.length
const mem = Array.from({ length: tlen + 1 }, () =>
new Array(slen + 1).fill(0)
)
for (let j = 0; j <= slen; j++) {
mem[0][j] = 1
}
for (let i = 0; i < tlen; i++) {
for (let j = 0; j < slen; j++) {
if (t.charAt(i) === s.charAt(j)) {
mem[i + 1][j + 1] = mem[i][j] + mem[i + 1][j]
} else {
mem[i + 1][j + 1] = mem[i + 1][j]
}
}
}
return mem[tlen][slen]
}
``````
Copy The Code &

Input

cmd
s = "rabbbit", t = "rabbit"

Output

cmd
3

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
const numDistinct = function(s, t) {
const tlen = t.length
const slen = s.length
const mem = Array.from({ length: tlen + 1 }, () =>
new Array(slen + 1).fill(0)
)
for (let j = 0; j <= slen; j++) {
mem[0][j] = 1
}
for (let i = 0; i < tlen; i++) {
for (let j = 0; j < slen; j++) {
if (t.charAt(i) === s.charAt(j)) {
mem[i + 1][j + 1] = mem[i][j] + mem[i + 1][j]
} else {
mem[i + 1][j + 1] = mem[i + 1][j]
}
}
}
return mem[tlen][slen]
}
``````
Copy The Code &

Input

cmd
s = "babgbag", t = "bag"

Output

cmd
5

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _115_DistinctSubsequences
{
public int NumDistinct(string s, string t)
{
if (string.IsNullOrEmpty(t)) return 1;
if (string.IsNullOrEmpty(s)) return 0;

var dp = new int[t.Length + 1, s.Length + 1];
for (int i = 0; i <= s.Length; i++)
dp[0, i] = 1;
for (int i = 0; i < t.Length; i++)
{
for (int j = i; j < s.Length; j++)
{
if (t[i] == s[j]) dp[i + 1, j + 1] = dp[i + 1, j] + dp[i, j];
else dp[i + 1, j + 1] = dp[i + 1, j];
}
//  Fast Prune
if (dp[i + 1, s.Length - (t.Length - i) + 1] == 0) return 0;
}

return dp[t.Length, s.Length];
}
}
}
``````
Copy The Code &

Input

cmd
s = "babgbag", t = "bag"

Output

cmd
5