Description:
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.
Examples:
Example 1:
Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from s.
Example 2:
Input: s = "babgbag", t = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from s.Solution in Python:
To solve this problem, you can use dynamic programming to count the number of distinct subsequences of string s that match string t. The idea is to use a 2D array dp where dp[i][j] represents the number of distinct subsequences of s[0..i-1] that match t[0..j-1].
Python
class Solution:
def numDistinct(self, s: str, t: str) -> int:
# Get the lengths of the input strings
m, n = len(s), len(t)
# Create a 2D dp array initialized with 0s
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Every string (including the empty string) has exactly one subsequence equal to the empty string
for i in range(m + 1):
dp[i][0] = 1
# Fill the dp array
for i in range(1, m + 1):
for j in range(1, n + 1):
# If the current characters in s and t match, we have two options:
# 1. Exclude the current character of s and use the result of dp[i-1][j]
# 2. Include the current character of s and use the result of dp[i-1][j-1]
if s[i - 1] == t[j - 1]:
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]
else:
# If the characters do not match, we only consider the result of excluding the current character of s
dp[i][j] = dp[i - 1][j]
# The result is the value in the bottom-right corner of the dp array
return dp[m][n]Explanation:
- Initialization:
mandnare the lengths of stringssandt, respectively.dpis a 2D list (matrix) of size(m+1) x (n+1)initialized with zeros.dp[i][0]is set to 1 for allibecause an emptytcan always be formed by any prefix ofs(including the empty prefix).
- Filling the DP Table:
- Iterate through each character of
s(from 1 tom) and each character oft(from 1 ton). - If
s[i-1] == t[j-1], updatedp[i][j]with the sum ofdp[i-1][j]anddp[i-1][j-1]. This means you can either exclude or include the current character ofsto formt[0..j-1]. - If
s[i-1] != t[j-1], updatedp[i][j]withdp[i-1][j], meaning you can only exclude the current character ofs.
- Iterate through each character of
- Result:
- The value
dp[m][n]represents the number of distinct subsequences ofsthat equalt.
- The value
This approach efficiently computes the number of distinct subsequences using dynamic programming with a time complexity of O(m * n), where m and n are the lengths of s and t, respectively.
Solution in Javascript:
JavaScript
/**
* @param {string} s
* @param {string} t
* @return {number}
*/
var numDistinct = function(s, t) {
// Get the lengths of the input strings
const m = s.length;
const n = t.length;
// Create a 2D dp array initialized with 0s
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
// Every string (including the empty string) has exactly one subsequence equal to the empty string
for (let i = 0; i <= m; i++) {
dp[i][0] = 1;
}
// Fill the dp array
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
// If the current characters in s and t match, we have two options:
// 1. Exclude the current character of s and use the result of dp[i-1][j]
// 2. Include the current character of s and use the result of dp[i-1][j-1]
if (s[i - 1] === t[j - 1]) {
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
} else {
// If the characters do not match, we only consider the result of excluding the current character of s
dp[i][j] = dp[i - 1][j];
}
}
}
// The result is the value in the bottom-right corner of the dp array
return dp[m][n];
};Solution in Java:
Java
class Solution {
public int numDistinct(String s, String t) {
// Get the lengths of the input strings
int m = s.length();
int n = t.length();
// Create a 2D dp array initialized with 0s
int[][] dp = new int[m + 1][n + 1];
// Every string (including the empty string) has exactly one subsequence equal to the empty string
for (int i = 0; i <= m; i++) {
dp[i][0] = 1;
}
// Fill the dp array
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// If the current characters in s and t match, we have two options:
// 1. Exclude the current character of s and use the result of dp[i-1][j]
// 2. Include the current character of s and use the result of dp[i-1][j-1]
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
} else {
// If the characters do not match, we only consider the result of excluding the current character of s
dp[i][j] = dp[i - 1][j];
}
}
}
// The result is the value in the bottom-right corner of the dp array
return dp[m][n];
}
}Solution in C#:
C#
public class Solution {
public int NumDistinct(string s, string t) {
int m = s.Length;
int n = t.Length;
// Create a 2D dp array initialized with 0s
int[,] dp = new int[m + 1, n + 1];
// Every string (including the empty string) has exactly one subsequence equal to the empty string
for (int i = 0; i <= m; i++) {
dp[i, 0] = 1;
}
// Fill the dp array
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// If the current characters in s and t match, we have two options:
// 1. Exclude the current character of s and use the result of dp[i-1, j]
// 2. Include the current character of s and use the result of dp[i-1, j-1]
if (s[i - 1] == t[j - 1]) {
dp[i, j] = dp[i - 1, j] + dp[i - 1, j - 1];
} else {
// If the characters do not match, we only consider the result of excluding the current character of s
dp[i, j] = dp[i - 1, j];
}
}
}
// The result is the value in the bottom-right corner of the dp array
return dp[m, n];
}
}