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.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.Given two strings s
and t
, find the number of distinct subsequences of s
that are equal to t
. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
This problem can be efficiently solved using dynamic programming. We create a 2D array dp
where dp[i][j]
represents the number of distinct subsequences of the first i
characters of s
that are equal to the first j
characters of t
.
Base Cases:
dp[i][0] = 1
for all i
, because there's always one way to form an empty subsequence.dp[0][j] = 0
for all j > 0
, because you can't form a non-empty subsequence from an empty string.Recursive Relation:
s[i-1] == t[j-1]
, it means the last characters match. We can either include the last character of s
in the subsequence (adding to the count from dp[i-1][j-1]
) or exclude it (keeping the count from dp[i-1][j]
). Therefore, dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
.s[i-1] != t[j-1]
, we cannot include the last character of s
, so dp[i][j] = dp[i-1][j]
.Final Result:
The final answer is dp[m][n]
, where m
is the length of s
and n
is the length of t
.
m
and n
are the lengths of strings s
and t
respectively. We iterate through the dp
array of size (m+1) * (n+1).dp
array. However, this can be optimized to O(n) by using only one row of the dp
array (as shown in Solution 2).Solution 1 (using O(m*n) space):
Python:
class Solution:
def numDistinct(self, s: str, t: str) -> int:
m, n = len(s), len(t)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = 1
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]
Java:
class Solution {
public int numDistinct(String s, String t) {
int m = s.length(), n = t.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; ++i) dp[i][0] = 1;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (s.charAt(i - 1) == t.charAt(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];
}
}
C++:
class Solution {
public:
int numDistinct(string s, string t) {
int m = s.length(), n = t.length();
vector<vector<long long>> dp(m + 1, vector<long long>(n + 1, 0));
for (int i = 0; i <= m; ++i) dp[i][0] = 1;
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];
}
};
Go:
func numDistinct(s string, t string) int {
m, n := len(s), len(t)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
dp[i][0] = 1
}
for i := 1; i <= m; i++ {
for 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]
}
TypeScript:
function numDistinct(s: string, t: string): number {
const m = s.length;
const n = t.length;
const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 0; i <= m; i++) dp[i][0] = 1;
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];
};
Rust:
impl Solution {
pub fn num_distinct(s: String, t: String) -> i32 {
let m = s.len();
let n = t.len();
let mut dp = vec![vec![0; n + 1]; m + 1];
for i in 0..=m {
dp[i][0] = 1;
}
for i in 1..=m {
for j in 1..=n {
if s.chars().nth(i - 1).unwrap() == t.chars().nth(j - 1).unwrap() {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
dp[m][n] as i32
}
}
Solution 2 (optimized space complexity to O(n)):
This solution uses only one row of the dp
array, reducing space complexity. The logic remains the same.
Python:
class Solution:
def numDistinct(self, s: str, t: str) -> int:
n = len(t)
dp = [0] * (n + 1)
dp[0] = 1
for i in range(len(s)):
for j in range(n, 0, -1):
if s[i] == t[j - 1]:
dp[j] += dp[j - 1]
return dp[n]
(Java, C++, Go, TypeScript examples are similar and follow the same space-optimized approach, iterating through the dp
array from the end to avoid overwriting values needed in the current iteration).
This detailed explanation and code examples should help you understand the solution to this problem effectively. Remember to choose the solution that best fits your needs regarding space optimization. For larger inputs, Solution 2's space efficiency becomes a significant advantage.