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

  • 2

    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 {
                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];    

Log in to reply

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