115. Distinct subsequences
115_solution1_tab.c
#include <stdlib.h>
#include <string.h>
int numDistinct(char *s, char *t) {
int n = strlen(s), m = strlen(t);
int w = m + 1;
// dp[i * w + j]; unsigned so intermediate overflow wraps instead of being UB
unsigned long long *dp = calloc((n + 1) * w, sizeof(unsigned long long));
for (int i = 0; i <= n; i++)
dp[i * w] = 1; // empty t: one way
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i * w + j] = dp[(i - 1) * w + j]; // skip cur s[i-1]
if (s[i - 1] == t[j - 1])
dp[i * w + j] += dp[(i - 1) * w + (j - 1)]; // pick it
}
}
int res = (int)dp[n * w + m];
free(dp);
return res;
}115_solution2_memo.c
#include <stdlib.h>
#include <string.h>
static const char *S, *T;
static int w;
static long long *dp; // dp[i * w + j], -1 = not computed
static long long f(int i, int j) {
if (j == 0)
return 1; // t fully matched
if (i == 0)
return 0; // s ran out first
if (dp[i * w + j] != -1)
return dp[i * w + j];
long long ways = f(i - 1, j); // skip s[i-1]
if (S[i - 1] == T[j - 1])
ways += f(i - 1, j - 1); // pick it
// keep within u32 range so nothing overflows and -1 stays a free sentinel
return dp[i * w + j] = ways & 0xFFFFFFFFLL;
}
int numDistinct(char *s, char *t) {
int n = strlen(s), m = strlen(t);
S = s, T = t, w = m + 1;
dp = malloc((n + 1) * w * sizeof(long long));
for (int k = 0; k < (n + 1) * w; k++)
dp[k] = -1;
int res = (int)f(n, m);
free(dp);
return res;
}115_solution1_tab.cpp
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
int numDistinct(string s, string t) {
int n = s.size(), m = t.size();
vector<vector<unsigned long long>> dp(n + 1,
vector<unsigned long long>(m + 1, 0));
for (int i = 0; i <= n; i++)
dp[i][0] = 1; // empty t: one way
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = dp[i - 1][j]; // skip cur s[i-1]
if (s[i - 1] == t[j - 1])
dp[i][j] += dp[i - 1][j - 1]; // pick it
}
}
return (int)dp[n][m];
}
};115_solution2_memo.cpp
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
int f(int i, int j, string &s, string &t, vector<vector<int>> &dp) {
if (j == 0)
return 1; // t fully matched
if (i == 0)
return 0; // s ran out first
if (dp[i][j] != -1)
return dp[i][j];
long long ways = f(i - 1, j, s, t, dp); // skip s[i-1]
if (s[i - 1] == t[j - 1])
ways += f(i - 1, j - 1, s, t, dp); // pick it
return dp[i][j] = (int)ways;
}
int numDistinct(string s, string t) {
int n = s.size(), m = t.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
return f(n, m, s, t, dp);
}
};115_solution1_tab.go
package dp
func numDistinct(s string, t string) int {
n, m := len(s), len(t)
dp := make([][]uint64, n+1) // uint64 so intermediate overflow wraps
for i := range dp {
dp[i] = make([]uint64, m+1)
dp[i][0] = 1 // empty t: one way
}
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
dp[i][j] = dp[i-1][j] // skip cur s[i-1]
if s[i-1] == t[j-1] {
dp[i][j] += dp[i-1][j-1] // pick it
}
}
}
return int(int32(dp[n][m]))
}115_solution2_memo.go
package dp
func numDistinct(s string, t string) int {
n, m := len(s), len(t)
dp := make([][]int, n+1) // -1 = not computed
for i := range dp {
dp[i] = make([]int, m+1)
for j := range dp[i] {
dp[i][j] = -1
}
}
var f func(i, j int) int
f = func(i, j int) int {
if j == 0 {
return 1 // t fully matched
}
if i == 0 {
return 0 // s ran out first
}
if dp[i][j] != -1 {
return dp[i][j]
}
ways := f(i-1, j) // skip s[i-1]
if s[i-1] == t[j-1] {
ways += f(i-1, j-1) // pick it
}
dp[i][j] = ways & 0xFFFFFFFF // keep within u32 range so nothing overflows
return dp[i][j]
}
return int(int32(f(n, m)))
}115_solution1_tab.java
class Solution {
public int numDistinct(String s, String t) {
int n = s.length(), m = t.length();
long[][] dp = new long[n + 1][m + 1];
for (int i = 0; i <= n; i++)
dp[i][0] = 1; // empty t: one way
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = dp[i - 1][j]; // skip cur s[i-1]
if (s.charAt(i - 1) == t.charAt(j - 1))
dp[i][j] += dp[i - 1][j - 1]; // pick it
}
}
return (int) dp[n][m];
}
}115_solution2_memo.java
import java.util.Arrays;
class Solution {
private long[][] dp; // -1 = not computed
private long f(int i, int j, String s, String t) {
if (j == 0)
return 1; // t fully matched
if (i == 0)
return 0; // s ran out first
if (dp[i][j] != -1)
return dp[i][j];
long ways = f(i - 1, j, s, t); // skip s[i-1]
if (s.charAt(i - 1) == t.charAt(j - 1))
ways += f(i - 1, j - 1, s, t); // pick it
// keep within u32 range so nothing overflows and -1 stays a free sentinel
return dp[i][j] = ways & 0xFFFFFFFFL;
}
public int numDistinct(String s, String t) {
int n = s.length(), m = t.length();
dp = new long[n + 1][m + 1];
for (long[] row : dp)
Arrays.fill(row, -1);
return (int) f(n, m, s, t);
}
}115_solution1_tab.js
/**
* @param {string} s
* @param {string} t
* @return {number}
*/
var numDistinct = function (s, t) {
const n = s.length, m = t.length;
const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));
for (let i = 0; i <= n; i++) dp[i][0] = 1; // empty t: one way
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
dp[i][j] = dp[i - 1][j]; // skip cur s[i-1]
if (s[i - 1] === t[j - 1]) dp[i][j] += dp[i - 1][j - 1]; // pick it
}
}
return dp[n][m];
};115_solution2_memo.js
/**
* @param {string} s
* @param {string} t
* @return {number}
*/
var numDistinct = function (s, t) {
const n = s.length, m = t.length;
const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(-1));
const f = (i, j) => {
if (j === 0) return 1; // t fully matched
if (i === 0) return 0; // s ran out first
if (dp[i][j] !== -1) return dp[i][j];
let ways = f(i - 1, j); // skip s[i-1]
if (s[i - 1] === t[j - 1]) ways += f(i - 1, j - 1); // pick it
return (dp[i][j] = ways);
};
return f(n, m);
};115_solution1_tab.py
class Solution:
def numDistinct(self, s: str, t: str) -> int:
n, m = len(s), len(t)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = 1 # empty t: one way
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = dp[i - 1][j] # skip cur s[i-1]
if s[i - 1] == t[j - 1]:
dp[i][j] += dp[i - 1][j - 1] # pick it
return dp[n][m]115_solution2_memo.py
import sys
class Solution:
def numDistinct(self, s: str, t: str) -> int:
n, m = len(s), len(t)
sys.setrecursionlimit(max(1000, n + 100)) # depth can reach len(s)
dp = [[-1] * (m + 1) for _ in range(n + 1)]
def f(i: int, j: int) -> int:
if j == 0:
return 1 # t fully matched
if i == 0:
return 0 # s ran out first
if dp[i][j] != -1:
return dp[i][j]
ways = f(i - 1, j) # skip s[i-1]
if s[i - 1] == t[j - 1]:
ways += f(i - 1, j - 1) # pick it
dp[i][j] = ways
return ways
return f(n, m)115_solution1_tab.rs
impl Solution {
pub fn num_distinct(s: String, t: String) -> i32 {
let (s, t) = (s.as_bytes(), t.as_bytes());
let (n, m) = (s.len(), t.len());
let mut dp = vec![vec![0u64; m + 1]; n + 1];
for i in 0..=n {
dp[i][0] = 1; // empty t: one way
}
for i in 1..=n {
for j in 1..=m {
dp[i][j] = dp[i - 1][j]; // skip cur s[i-1]
if s[i - 1] == t[j - 1] {
// pick it; wrapping: intermediates may overflow
dp[i][j] = dp[i][j].wrapping_add(dp[i - 1][j - 1]);
}
}
}
dp[n][m] as i32
}
}115_solution2_memo.rs
impl Solution {
pub fn num_distinct(s: String, t: String) -> i32 {
let (s, t) = (s.as_bytes(), t.as_bytes());
let mut dp = vec![vec![None; t.len() + 1]; s.len() + 1]; // None = not computed
Self::f(s.len(), t.len(), s, t, &mut dp) as i32
}
fn f(i: usize, j: usize, s: &[u8], t: &[u8], dp: &mut Vec<Vec<Option<u32>>>) -> u32 {
if j == 0 {
return 1; // t fully matched
}
if i == 0 {
return 0; // s ran out first
}
if let Some(ways) = dp[i][j] {
return ways;
}
let mut ways = Self::f(i - 1, j, s, t, dp); // skip s[i-1]
if s[i - 1] == t[j - 1] {
// pick it; wrapping: intermediates may overflow
ways = ways.wrapping_add(Self::f(i - 1, j - 1, s, t, dp));
}
dp[i][j] = Some(ways);
ways
}
}