LeetCode: Distinct Subsequences [115]

Hello everyone , I meet you again , I'm the king of the whole stack , I've prepared for you today Idea Registration code .

【 The title of 】

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.

【 The question 】

Given string S and T, By deleting S Several characters in can get T, be T be called S The subsequence . How many deletion methods can be obtained T

【 Ideas 】

DP problem . Definition A[i][j] (i>j) Express S[1…i] Convert to T[1…j] The number of ways ( There is only one type of operation . That's from S Delete several characters from ). The conversion equation is as follows ： hypothesis S[i]==T[j], A[i][j]=A[i-1][j-1]+A[i-1][j]; hypothesis S[i]!=T[j], A[i][j]=A[i-1][j]; Initialization matrix The starting point A[0][0]=1; first line A[0][i]=0; First column A[i][j]=1;

【 Code 】

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;          // hypothesis S==T, return 1,  I think so 1 There are two ways of transformation 
        
        vector<vector<int> >matrix(S.length()+1, vector<int>(T.length()+1, 0));
        // initialization matrix[0][0]
        matrix[0][0]=1;
        // Initialize diagonal 
        for(int j=1; j<=T.length(); j++)
            matrix[0][j]=0;
        // Initialize the first column 
        for(int i=1; i<=S.length(); i++)
            matrix[i][0]=1;
            
        // Consider others i>j The situation of 
        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()];
    }
};

Copy

Copyright notice ： This article is an original blog article . Blog , Without consent , Shall not be reproduced .

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/117649.html Link to the original text ：https://javaforall.cn