From LeetCode
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.
I see a very good DP solution, however, I have hard time to understand it, anybody can explain how this dp works?
int numDistinct(string S, string T) {
vector<int> f(T.size()+1);
//set the last size to 1.
f[T.size()]=1;
for(int i=S.size()-1; i>=0; --i){
for(int j=0; j<T.size(); ++j){
f[j]+=(S[i]==T[j])*f[j+1];
printf("%d\t", f[j] );
}
cout<<"\n";
}
return f[0];
}
First, try to solve the problem yourself to come up with a naive implementation:
Let's say that S.length = m
and T.length = n
. Let's write S{i}
for the substring of S
starting at i
. For example, if S = "abcde"
, S{0} = "abcde"
, S{4} = "e"
, and S{5} = ""
. We use a similar definition for T
.
Let N[i][j]
be the distinct subsequences for S{i}
and T{j}
. We are interested in N[0][0]
(because those are both full strings).
There are two easy cases: N[i][n]
for any i
and N[m][j]
for j<n
. How many subsequences are there for ""
in some string S
? Exactly 1. How many for some T
in ""
? Only 0.
Now, given some arbitrary i
and j
, we need to find a recursive formula. There are two cases.
If S[i] != T[j]
, we know that N[i][j] = N[i+1][j]
(I hope you can verify this for yourself, I aim to explain the cryptic algorithm above in detail, not this naive version).
If S[i] = T[j]
, we have a choice. We can either 'match' these characters and go on with the next characters of both S
and T
, or we can ignore the match (as in the case that S[i] != T[j]
). Since we have both choices, we need to add the counts there: N[i][j] = N[i+1][j] + N[i+1][j+1]
.
In order to find N[0][0]
using dynamic programming, we need to fill the N
table. We first need to set the boundary of the table:
N[m][j] = 0, for 0 <= j < n
N[i][n] = 1, for 0 <= i <= m
Because of the dependencies in the recursive relation, we can fill the rest of the table looping i
backwards and j
forwards:
for (int i = m-1; i >= 0; i--) {
for (int j = 0; j < n; j++) {
if (S[i] == T[j]) {
N[i][j] = N[i+1][j] + N[i+1][j+1];
} else {
N[i][j] = N[i+1][j];
}
}
}
We can now use the most important trick of the algorithm: we can use a 1-dimensional array f
, with the invariant in the outer loop: f = N[i+1];
This is possible because of the way the table is filled. If we apply this to my algorithm, this gives:
f[j] = 0, for 0 <= j < n
f[n] = 1
for (int i = m-1; i >= 0; i--) {
for (int j = 0; j < n; j++) {
if (S[i] == T[j]) {
f[j] = f[j] + f[j+1];
} else {
f[j] = f[j];
}
}
}
We're almost at the algorithm you gave. First of all, we don't need to initialize f[j] = 0
. Second, we don't need assignments of the type f[j] = f[j]
.
Since this is C++
code, we can rewrite the snippet
if (S[i] == T[j]) {
f[j] += f[j+1];
}
to
f[j] += (S[i] == T[j]) * f[j+1];
and that's all. This yields the algorithm:
f[n] = 1
for (int i = m-1; i >= 0; i--) {
for (int j = 0; j < n; j++) {
f[j] += (S[i] == T[j]) * f[j+1];
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With