Distinct Subsequences
Given two strings s and t, return the number of distinct subsequences of s which equals t.
Example:
Input: s = "babgbag", t = "bag"
Output: 5
As shown below, there are 5 ways you can generate "bag" from s.
- babgbag
- babgbag
- babgbag
- babgbag
- babgbag
Code
// s: babgbag -> iterated by pointer j
// t: bag -> iterated by pointer i
public int numDistinct(String s, String t) {
int S = s.length(), T = t.length();
int[][] dp = new int[T + 1][S + 1];
for (int j = 0; j <= S; j++) {
dp[0][j] = 1;
}
for (int i = 1; i <= T; i++) {
for (int j = 1; j <= S; j++) {
if (s.charAt(j - 1) == t.charAt(i - 1)) {
dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
} else {
dp[i][j] = dp[i][j - 1];
}
}
}
return dp[S][T];
}State transition
Fill in the DP table row by row. When dealing with a row,
assume t (the shorter string) is fixed and s is increasing in character.
Try clicking on different values to show how they are calculated.
| "" | b | a | b | g | b | a | g | |
|---|---|---|---|---|---|---|---|---|
| "" | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| b | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 3 |
| a | 0 | 0 | 1 | 1 | 1 | 1 | 4 | 4 |
| g | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 5 |