115. Distinct Subsequences
Đề Bài
Given two strings s and t, return the number of distinct subsequences 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.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.
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n×m)
💾 Không gian
O(n×m)
Lời Giải
C++
0115-distinct-subsequences.cpp
class Solution {
public:
int numDistinct(string s, string t) {
int n = s.size(), m = t.size();
vector<vector<unsigned int>> dp(n + 1, vector<unsigned int>(m + 1));
for (int i = 0; i <= n; ++i) {
dp[i][0] = 1;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
dp[i][j] = dp[i - 1][j];
if (s[i - 1] == t[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}
}
}
return dp[n][m];
}
};