LeetCode Problem : Distinct Subsequences

Problem

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.

Code

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 < n)
    return 0;
    if( n == 0)
    return 0;
    vector<vector<bool> > p(m,vector<bool>(n,false));
    vector<vector<int> > M(m,vector<int>(n,0));
    if(S[0] == T[0]){
        p[0][0] = true;
        M[0][0] = 1;
    }
    for(int i = 1; i < m; ++i){
        if(S[i] == T[0]){
            p[i][0] = true;
            M[i][0] = M[i - 1][0] + 1;
        }
        else{
            p[i][0] = p[i - 1][0];
            M[i][0] = M[i - 1][0];
        }
    }
    for(int i = 1; i < m; ++i){
        int num = min(i + 1,n);
        for(int j = 1; j < num; ++j){
            if(S[i] == T[j] && p[i - 1][j]){
                M[i][j] = M[i - 1][j] + M[i - 1][j - 1];
                p[i][j] = true;
            }
            else if(S[i] == T[j] && p[i - 1][j - 1]){
                M[i][j] = M[i - 1][j - 1];
                p[i][j] = true;
            }
            else if(S[i] != T[j] && p[i - 1][j]){
                M[i][j] = M[i - 1][j];
                p[i][j] = true;
            }
        }
    }
    return M[m - 1][n - 1];
}