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.

方法一：用回溯法实现，时间复杂度很高，空间复杂度低，对于小数据可以通过，对大数据会出现Time Limit Exceeded

1 int num=0; 2 void countnum(string S, string T) { 3     if(T.size()==0) 4     { 5         num++; 6         return; 7      } 8             9      for(int i=0; i

 

 

方法二：用动态规划（DP）实现，需要的空间复杂度为O(N*M)，对于大数据也可以很快处理。

1 class Solution { 2 public: 3     int numDistinct(string S, string T) { 4         vector
     
      
        > num(S.size()+1,vector
       
        (T.size()+1,0)); //num[i][j]表示T中的前j个字符构成的子字符串在S中的前i个字符中出现的次数,num[i][j]满足: 5         S = " "+ S;                                                                                 //（1）若S[i]=T[j]，则num[i][j] = num[i-1][j]+num[i-1][j-1]； 6         T = " "+ T;                                                                                 //（2）若S[i]!=T[j]，则num[i][j] = num[i-1][j]； 7         num[0][0]=1;                                                                                //（3）若j>i，则num[i][j]=0。 8         for(int i=1; i
        
         i)12                 {13                     num[i][j]=0;14                     break;15                 }16                 if(S[i]==T[j])17                     num[i][j] = num[i-1][j] + num[i-1][j-1];18                 else19                     num[i][j] = num[i-1][j];20             }21             return num[S.size()-1][T.size()-1];22 23     }24 };