首页 > 代码库 > LeetCode: Distinct Subsequences [115]

LeetCode: Distinct Subsequences [115]

2024-07-07 05:17:03   220人阅读

【题目】


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.



【题意】

    给定字符串S和T，通过删除S中的若干个字符可以得到T，则T称为S的子序列，问有多少种删法可以得到T


【思路】


    DP问题。
    定义A[i][j] (i>j)表示S[1...i]转化到T[1...j]的方式数(操作类型只有一种，那就是从S中删除若干字符)。
    转换方程如下：
        如果S[i]==T[j], A[i][j]=A[i-1][j-1]+A[i-1][j];
        如果S[i]!=T[j], A[i][j]=A[i-1][j];
        
    初始化矩阵
        起始点A[0][0]=1;
        第一行A[0][i]=0;
        第一列A[i][j]=1;


【代码】

class Solution {
public:
    int numDistinct(string S, string T) {
        if(S.length()==0 || S.length()==0)return 0;
        if(S.length()<T.length())return 0;          //如果S==T,返回1， 认为有1种转换方式
        
        vector<vector<int> >matrix(S.length()+1, vector<int>(T.length()+1, 0));
        //初始化matrix[0][0]
        matrix[0][0]=1;
        //初始化对角线
        for(int j=1; j<=T.length(); j++)
            matrix[0][j]=0;
        //初始化第一列
        for(int i=1; i<=S.length(); i++)
            matrix[i][0]=1;
            
        //考虑其他i>j的情况
        for(int i=1; i<=S.length(); i++){
            for(int j=1; j<=T.length(); j++){
                if(S[i-1]==T[j-1])matrix[i][j]=matrix[i-1][j-1]+matrix[i-1][j];
                else matrix[i][j]=matrix[i-1][j];
            }
        }
        return matrix[S.length()][T.length()];
    }
};


联系
我们