首页 > 代码库 > Distinct Subsequences

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.

思路:看了半天题目,才明白,原来是计算子序列在原始字符串里通过删除字符来得到的,能得到多少种这样的子序列字符串。

这道题使用动态规划的思路来解题。我们使用dp[i][j]来表示S的前i个字符和T的前j个字符匹配子串的个数。

1.初始条件:T为空时,S中的任一个都可匹配,所以dp[i][0]=1;S为空,T中任意都不可以匹配,dp[0][j]=0;

2.若S的第i个字符和T的第j个字符匹配时,我们可以知道,一是S的前i-1个字符匹配T的前j-1个字符,二是S的前i-1个字符已经匹配T的前j个字符,则有如下表达式dp[i][j]=dp[i-1][j-1]+dp[i-1][j].

3.若S的第i个字符和T的第j个字符不匹配,说明S的第i-1个字符子串已与T的第j个字符子串匹配,则dp[i][j]=dp[i-1][j];

class Solution {
public:
    int numDistinct(string S, string T) {
        int len_s=S.size();
        int len_t=T.size();
        if(len_s<len_t)
            return 0;
        vector<vector<int> > dp(len_s+1,vector<int>(len_t+1,0));
        for(int i=0;i<=len_s;i++)
            dp[i][0]=1;
        for(int i=1;i<=len_s;i++)
        {
            for(int j=1;j<=len_t;j++)
            {
                if(S[i-1]==T[j-1])
                    dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
                else
                    dp[i][j]=dp[i-1][j];
            }
        }
        return dp[len_s][len_t];
    }
};