Algorithm
Problem Nmae: 115. Distinct Subsequences
Given two strings s and t, return the number of distinct
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.rabbbitrabbbitrabbbit
Example 2:
Input: s = "babgbag", t = "bag" Output: 5 Explanation: As shown below, there are 5 ways you can generate "bag" from s.babgbagbabgbagbabgbagbabgbagbabgbag
Constraints:
1 <= s.length, t.length <= 1000sandtconsist 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;
}
Input
s = "rabbbit", t = "rabbit"
Output
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]
}
Input
s = "rabbbit", t = "rabbit"
Output
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]
}
Input
s = "babgbag", t = "bag"
Output
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];
}
}
}
Input
s = "babgbag", t = "bag"
Output
5