Distinct Subsequences

07/11/2016 String Dynamic Programming

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.


Solution

Result: Accepted Time: 0 ms

Here should be some explanations.

#define MAXN 1024
int dp[2][MAXN];
void shorter(char *s,char * t)
{
    bool exist[256]={0};
    for(; *t; t++)
        exist[*t] = true;
    char *ptr = s--;
    while(*(++s))
        if(exist[*s])
            *(ptr++) = *s;
    *ptr = 0;
}
int numDistinct(char* s, char* t) {
    shorter(s,t);
    const int slen = strlen(s), tlen = strlen(t);
    dp[0][0] = (s[0]==t[0]);
    for(int i = 1; i < slen; i++)
        dp[0][i] = (s[i] == t[0])+dp[0][i-1];
    if(slen < tlen) return 0;
    for(int r = 1; r < tlen; r++)
    {
        for(int i = 0 ; i < r; i++)
            dp[r&1][i] = 0;
        for(int c = r; c < slen; c++)
            if(t[r]==s[c])
                dp[r&1][c] = dp[(r-1)&1][c-1] + dp[r&1][c-1];
            else
                dp[r&1][c] = dp[r&1][c-1];
    }
    return dp[(tlen-1)&1][slen-1];
}

Complexity Analytics

  • Time Complexity:
  • Space Complexity: