Question
Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.
Stats
| Frequency | 2 |
| Difficulty | 4 |
| Adjusted Difficulty | 5 |
| Time to use | -------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
This is an extremely difficult DP question, probably the most difficult DP on leetcode.
Normally, string matching question is best solved with DP, so is this question. The problem is how to construct the Bellman equation (also known as dynamic programming equation).
Updated on June 24th, I listed down one example using S = “abab” and T = “ab”.
| {} | a | b | |
|---|---|---|---|
| {} | 1 | 0 | 0 |
| a | 1 | 1 | 0 |
| b | 1 | 1 | 1 |
| a | 1 | 2 | 1 |
| b | 1 | 2 | 3 |
Solution
It took me a really long time to understand, until I read this blog.
Let W(i, j) stand for the number of subsequences of S(0, i) in T(0, j). If S.charAt(i) == T.charAt(j), W(i, j) = W(i-1, j-1) + W(i-1,j); Otherwise, W(i, j) = W(i-1,j).
Two code are posted below, realizing this solution with 2D and 1D array respectively (first code is better).
Code
First, DP code
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 ++) {
for (int j = 0; j <= n; j ++) {
if (j == 0) dp[i][j] = 1;
else if (i == 0) dp[i][j] = 0;
else 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];
}
Second, same solution but reduced 2-D array to 1-D.
Code readability is reduced, however.
public int numDistinct(String S, String T) {
int m = S.length(), n = T.length();
int[] dp = new int[n + 1];
for (int i = 0; i <= m; i ++) {
for (int j = n; j >= 0; j --) {
if (j == 0)
dp[j] = 1;
else if (i == 0)
dp[j] = 0;
else if (S.charAt(i-1) == T.charAt(j-1))
dp[j] = dp[j-1] + dp[j];
}
}
return dp[n];
}