[LeetCode OJ] Distinct Subsequences

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<S.size(); i++)
10      {
11          if(S[i]==T[0])
12          {
13              string s2 = S.substr(i+1);
14              string t2 = T.substr(1);
15               countnum(s2, t2);
16           }
17               
18      }
19      return;
20 }
21 
22 class Solution {
23 public:
24     int numDistinct(string S, string T) {
25         countnum(S, T);
26         return num;
27     }
28 };

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

 1 class Solution {
 2 public:
 3     int numDistinct(string S, string T) {
 4         vector<vector<int> > num(S.size()+1,vector<int>(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<S.size(); i++)
 9             for(int j=0; j<T.size(); j++)
10             {
11                 if(j>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                 else
19                     num[i][j] = num[i-1][j];
20             }
21             return num[S.size()-1][T.size()-1];
22 
23     }
24 };