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.

 

接受了Edit Distance的教训，该用了vector<vector<int> >勉强过了大数据。f[i][j]表示S[i]和T[j]相同的情况下，产生的情况个数。

最后sum(f[i][T.size()]), 0<= i <= S.size()，就是结果了。

1 class Solution { 2 public: 3     int numDistinct(string S, string T) { 4         // Start typing your C/C++ solution below 5         // DO NOT write int main() function 6         vector
     
      
        > f(S.size()+1, vector
       
        (T.size()+1)); 7          8         f[0][0] = 1; 9         for(int i = 1; i <= S.size(); i++)10             f[i][0] = 0;11             12         for(int i = 1; i <= T.size(); i++)13             f[0][i] = 0;14             15         for(int i = 1; i <= S.size(); i++)16             for(int j = 1; j <= T.size(); j++)17                 if (S[i-1] == T[j-1])18                 {19                     f[i][j] = 0;20                     for(int k = 0; k < i; k++)21                         f[i][j] += f[k][j-1];22                 }23                 else24                     f[i][j] = 0;25         26         int sum = 0;27         for(int i = 0; i <= S.size(); i++)28             sum += f[i][T.size()];29             30         return sum;31     }32 };