115. Distinct Subsequences
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.
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
andt
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:
$$ f[i][j]=\left{ \begin{aligned} &f[i-1][j], &s[i-1] \ne t[j-1] \ &f[i-1][j-1]+f[i-1][j], &s[i-1]=t[j-1] \end{aligned} \right. $$
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)$.
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|