# My C++ solution (10 ms) O(n) space, O(mn) time n:T length, m: S length

• The idea is to implement a Finite State Machine (FSM) to track the number of distinct subsequences found at stage i. In the following code, Num is the array and Num[j] is the number of distinct subsequences found for (S[0::i-1], T[0:j-1]) (i.e. how many ways we can get T[0::j-1] from S[0::i-1]) at stage i-1. In the i for loop, it scans a new char S[i] and if S[i] == T[j] for some j, then that means all the subsequences of (S[0::i-1], T[0:j-1]) can become the subsequences of (S[0::i], T[0:j]) at stage i. So Num[j] = Num[j] + Num[j-1]. Otherwise, Num[j] keeps unchanged since no new subsequences are found. What we need to do is to scan S and update Num accordingly and output Num[tl] at the end.

``````       class Solution {
public:
int numDistinct(string S, string T) {
int sl = S.size(), tl = T.size();
if(tl==0) return 1; // if T is empty, return 1;
if(tl > sl) return 0; // if T is longer than S, return 0
if(tl == sl)  return S==T?1:0;

// if S is longer than T and T is not empty
vector<int>  Num(tl+1, 0); // array to save the number subsequences of (S[0::i], T[0::j-1])
Num[0] =1; // when S[i] == T[0], a new subsequence of (S[0::i], T[0::0]) is found
int i,j;

for(i =0; i<sl; i++)
{
for(j = tl; j > 0; j--)
{
if(S[i] == T[j-1])
Num[j] = Num[j-1] + Num[j];
}
}

return Num[tl];
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.