[Leetcode] Distinct Subsequences

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.

Pasted from <http://leetcode.com/onlinejudge>

Analysis:

If S[0] = T[0], then T is a subsequence of S if

• the rest of string T is a subsequence the rest of string S,  or

• T is a subsequence of the rest of string S

If S[0] != T[0], then T cannot be a subsequence of S; it could only be the subsequence  of the rest of S.

Let S'[i] be the suffix of S beginning from index i, and T'[j] be the suffix of T beginning from index j and f[i][j] is the number of subsequence of S'[i] and T'[j]. By the above analysis, we can get the transition function of DP as

• f[i][j] = f[i+1][j+1] + f[i+1][j], if S[i] == T[j]
• f[i][j] = f[i+1][j], if S[i] != T[j]

Now consider the end condition: if j reached the end of string T, that means, all chars in T has been satisfied in S  (from the transition function we  can notice that the j increased only when S[i] == T[j]), the subsequence has already been found in S. On the other hand, if the end of string S was reached, and end of string T was not, no subsequence was found.

• f[i][j] =1, if j == T.size()
• f[i][j] = 0, if I ==S.size() &&  j != T.size()

int numDistinct(string S, string T) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    int m = S.size();
    int n = T.size();
    if (m == 0 || n == 0)
        return 0;

    vector v(n + 1,0);
    vector > f(m + 1, v);

    for (int i=m; i>=0; i--)
    {
        for (int j=n; j>=0; j--)
        {
            if (j == n)
                f[i][j] = 1;
            else if (i == m)
                f[i][j] = 0;
            else if (S[i] != T[j])
                f[i][j] = f[i+1][j];
            else
                f[i][j] = f[i+1][j+1] + f[i+1][j];
        }
    }
    return f[0][0];
}