115. Distinct Subsequences
給定兩個字符串 s 和 t，返回 s 中等於 t 的不同子序列的數量。
測試用例生成的答案會適合32位有符號整數。
範例：
輸入：s = "rabbbit", t = "rabbit" 輸出：3 解釋： 如下所示，有3種方法可以從 s 生成 "rabbit"： rabbbit rabbbit rabbbit
Python
class Solution:
def numDistinct(self, s: str, t: str) -> int:
m, n = len(s), len(t)
# Create a 2D DP array with dimensions (m+1) x (n+1)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Every string has exactly one subsequence that equals an empty string
for i in range(m + 1):
dp[i][0] = 1
# Fill the DP table
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]
73.11MB, 286ms
C++
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
int numDistinct(string s, string t) {
int m = s.length();
int n = t.length();
// Create a 2D DP array with dimensions (m+1) x (n+1)
vector<vector<unsigned long long>> dp(m + 1, vector<unsigned long long>(n + 1, 0));
// Every string has exactly one subsequence that equals an empty string
for (int i = 0; i <= m; ++i) {
dp[i][0] = 1;
}
// Fill the DP table
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];
}
};
31.43MB, 31ms
Javascript
/**
* @param {string} s
* @param {string} t
* @return {number}
*/
var numDistinct = function(s, t) {
const m = s.length;
const n = t.length;
// Create a 2D DP array with dimensions (m+1) x (n+1)
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
// Every string has exactly one subsequence that equals an empty string
for (let i = 0; i <= m; ++i) {
dp[i][0] = 1;
}
// Fill the DP table
for (let i = 1; i <= m; ++i) {
for (let 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];
};
76.83MB, 141ms
