Distinct Subsequences (C++ code)

LeetCode Distinct Subsequences, Oct 19 '12

 难度4，出现频率2

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.

思路：first, so each letter in T, set up a list with position information. Second, set up an array A of size(T). Now iterate through S from end to start, for each element s, update A[i] where i is the position of s in T.
A[i] gives the number of subsequences containing the part starting from ith position of T.
（还是用英文好写，汗。）
例子： S = bababa     T = baa
step 1: pos[b] = {0}, pos[a] ={1,2} .
step 2:  array A[4], A[i] =0 for i<3, A[3]=1.
step3: for S[5] = a, A[1] += A[2] = 0; A[2] +=A[3] = 1;
          for S[4] = b, A[0] += A[1] = 0;
         for S[3] = a, A[1] += A[2] = 1, A[2] +=A[3] =2;
         for S[4] = b, A[0] = 1
        for S[5] = a, A[1] = 3, A[2] = 3
So the result is A[0 ]= 1.
 时间复杂度O(n), worst case O(mn), m=size(T), 代码如下：
----------------------------

 int numDistinct(string S, string T) {
      map<char, vector<int>> pos;
      vector<int> list;
      int i;
      for(i = 0; i < T.length(); i++){
         pos[T[i]].push_back(i);
      }
     int *A= new int[T.length()+1];
     memset(A,0,T.length()*sizeof(int));
     A[T.length()] = 1;
      for(i = S.length() - 1; i >= 0; i--){
          list = pos[S[i]];          
          for(int j = 0; j < list.size(); j++){
             A[list[j]] += A[list[j]+1];
          }
         
      } 
     i = A[0];
     delete [] A;

     return i;
    }