Given two strings s and t, return the number of distinctsubsequences 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.
babgbag
babgbagbabgbag
babgbag
babgbag
Constraints:
1 <= s.length, t.length <= 1000
s and t consist of English letters.
Solutions
Solution 1: Dynamic Programming
We define $f[i][j]$ as the number of schemes where the first $i$ characters of string $s$ form the first $j$ characters of string $t$. Initially, $f[i][0]=1$ for all $i \in [0,m]$.
When $i > 0$, we consider the calculation of $f[i][j]$:
When $s[i-1] \ne t[j-1]$, we cannot select $s[i-1]$, so $f[i][j]=f[i-1][j]$;
Otherwise, we can select $s[i-1]$, so $f[i][j]=f[i-1][j-1]$.
Therefore, we have the following state transition equation:
The final answer is $f[m][n]$, where $m$ and $n$ are the lengths of strings $s$ and $t$ respectively.
The time complexity is $O(m \times n)$, and the space complexity is $O(m \times n)$.
We notice that the calculation of $f[i][j]$ is only related to $f[i-1][..]$. Therefore, we can optimize the first dimension, reducing the space complexity to $O(n)$.
implSolution{#[allow(dead_code)]pubfnnum_distinct(s:String,t:String)->i32{letn=s.len();letm=t.len();letmutdp:Vec<Vec<u64>>=vec![vec![0;m+1];n+1];// Initialize the dp vectorforiin0..=n{dp[i][0]=1;}// Begin the actual dp processforiin1..=n{forjin1..=m{dp[i][j]=ifs.as_bytes()[i-1]==t.as_bytes()[j-1]{dp[i-1][j]+dp[i-1][j-1]}else{dp[i-1][j]};}}dp[n][m]asi32}}